【摘要】多式联运是指在一个包含多种运输方式的物流网络中（利用多种运输工具）将物品从初始地运到目的地的过程。随着现代物流的发展，多式联运越来越受到企业的重视。本文主要研究如何确定从起点到终点的总成本最小的多式联运路线的问题。这里的成本包括纯运输成本、中转成本、等待（仓储）成本等几部分。

在本文中，我们提出了一种方法将一个多式联运网络转换为一个时间－空间的普通网络。通过这种转换，原来多式联运网络中的确定从起点到终点的总成本最小的运输路线的问题则成为时间－空间网络中的最短路径问题。因此，多式联运的最小成本路线问题可以被有效地解决。

关键词：多式联运，最短路径，最小成本路线，优化

一．前言

       本论文主要考虑多式联运中的最小成本路线问题。假定有一批次货物需要通过一个包含多种运输方式的运输网络从起始地运输到某指定目的地，货物在起始地有最早出发时间限制，在目的地有最晚到达时间限制。也就是说，货物只能在最早出发时间之后从起始地出发，并在最晚到达时间之前到达目的地。实际应用中，最早出发时间通常对应于工厂的出厂时间，最晚到达时间对应于与客户约定的到货时间。运输过程中可以经过其它城市中转，并且两两城市之间有一种或多种运输方式可选。这些运输方式可以包括空运、海运、铁路运输、卡车运输等。运输网络中的每一航班都有固定的出发时间和运输时间。例如，广州到上海的飞机每天10：00点、12：00点、16：00点出发，航行时间是2个小时。我们允许货物在任何城市不同港口之间进行中转（转换运输工具及航班），但每次中转都有相应的中转成本和中转时间。其中，中转成本包括从当前运输工具上卸载下来的卸货费用、从当前港口运输到同一城市其他类型港口的运输费用、以及装载到下一运输工具上的装载费用。相应的，中转时间包括卸货时间、运输时间和装货时间。图1是一个简单的多模式联合运输网络示例。给定货物的起始地、目的地以及到达目的地的时间限制，我们的目标是要找到一条纯运输成本、中转成本、等待（仓储）成本的总和最小的多式联运路线。

       随着信息技术在物流领域的广泛应用以及企业间的信息共享，多式联运越来越具有可操作性，因此也逐渐受到企业界的重视。本文研究的动机来自飞利浦医疗器械有限公司对多式联运最小成本路线选择的需求。该公司是全球三大医疗器械制造商之一，在全球有7个生产工厂，分布在欧洲（4个）和美国（3个），产品包括X－光扫描仪、超声波扫描仪等等。这些设备通常体积较大，需要独立用集装箱运输。然而，当一个乡村（或中小城市）的医院定购这些设备时，单一的运输方式往往不能完成这种运输任务，因为绝大部分乡村（或中小城市）都没有机场和港口。因此，飞利浦公司就需要为这些订单选择合适的多式联运路线，一方面要使得总的运输成本最小，另一方面也要保证货物在规定的时间内到达客户手中。在理论研究方面，Kelleher 等（2003）研究了如何利用互联网信息产生合适的多式联运路线的问题。该研究主要侧重于系统开发及与互联网信息的结合方面。另外，Southworth 和Peterson （2000）描述了如何利用综合数据结构表示美国的多式联运网络。在模型方面，Febbraro 和Sacone (1995) 提出了一种寻找合适的多式联运路线的方法，该方法找到的最佳路线主要是基于当时的交通状况信息，并没有考虑航班的固定出发时间。Boussedjra 等（2004）提出了一种找到多式联运网络中两点间的最快路径（运输时间最短）的方法，但该方法并没有考虑运输成本。在本文中，我们解决的问题是找到在给定的运输时间限制下的两点间的最小成本的多式联运路线。我们提出了一种方法将一个多式联运网络转换为一个时间－空间的普通网络。通过这种转换，原问题则成为时间－空间网络中的最短路径问题，从而可以用标号法（Label Setting）有效地解决。