集装箱卡车运输问题的基于图的建模方法  

Graph-based modeling method for container truck transportation problems

作　　者：张瑞友[1] 汪定伟[1] 尹原永 

机构地区：[1]东北大学信息科学与工程学院流程工业综合自动化国家重点实验室,沈阳110819 [2]釜山国立大学工业工程系,釜山609735

出　　处：《系统工程理论与实践》2011年第8期1539-1545,共7页Systems Engineering-Theory & Practice

基　　金：中央高校基本科研业务费专项资金(N090304012);国家自然科学基金(71001019;70931001;60821063;71021061)

摘　　要：对港口和发货人/收货人之间的集装箱卡车运输问题给出了基于图的建模方法.该图不仅可以描述进出口空箱或满箱的运输,而且可以描述空集装箱作为运输资源的属性.这种图将确定的活动描述为顶点,将不确定的活动描述为弧,称为确定活动在顶点上的图(DAOV图).基于这种方法,建立了集装箱卡车运输问题的基本情形、多堆场多港口情形以及堆场上的空箱数目给定情形的数学模型;相应问题被描述为带时间窗的多旅行商问题(m-TSPTW)、多堆场的m-TSPTW以及带资源约束的m-TSPTW.而且这种方法可以扩展到集装箱卡车运输问题的更一般情形,这体现出该建模方法的有效性.A graph-based modeling method of container truck transportation problems between terminals and final shippers/receivers was proposed in this paper.The graph can formulate not only the transportation of import/export full/empty containers,but also the transportation resource attribute of empty containers. The graph denotes determinate activities with vertexes and denotes indeterminate activities with arcs.Therefore,it is named as determinate-activities-on-vertexes（DAOV） graph.Based on the proposed graph,the basic case,multi-depot multi-terminal case,and the case with given number of empty containers on depots,of the container truck transportation problems were mathematically modeled.They fall into the multiple traveling salesman problem with time windows（m-TSPTW）,multi-depot m-TSPTW,and m-TSPTW with resource constraints,respectively.Furthermore,the modeling method can be extended to more general cases of the problems,which indicates the validity of the presented graph-based modeling method.

关 键 词：集装箱卡车运输 运输资源 多旅行商问题 图 时间窗 

分 类 号：TP2[自动化与计算机技术—检测技术与自动化装置]