Optimal Intermodal Transport Path Planning Based on Martins Algorithm
-
摘要: 为了快速高效地找出最优的联运路径,在现有模型的基础上,考虑时间窗约束,建立了具有多目标、多运输方式、多货种的路径选择改进模型,并设计了2层搜索算法求解该模型.第1层在已知每条路径标签的基础上,根据时间窗删除规则并利用改进的Martins算法,计算出有效路径集;第2层将第1层的有效解作为其初始解,删除不满足货物运输总时间、中转次数和运输方式容量3个限制条件的路径,得到最优路径集合.根据货主的需求,采用序数偏好方法,组合不同的费用权重和时间权重得到综合权重值,找出对应最大综合权重值的最优路径.实例分析表明:相比已有的标签算法,改进算法增加了运算方式容量限制条件,缩小了解空间,避免了生成无效路径;相比拉格朗日松弛算法只能求得解的上下限,本文算法能够求得精确解,耗时在30 s以内,计算时间减少75%.Abstract: In order to select optimal paths quickly and efficiently, a multi-objective multimodal multi-commodity routing model with time windows was proposed on the basis of the existing model. A two-layer search algorithm was designed to solve the model. In the first layer, a revised Martins label setting algorithm and two time constraints are combined to calculate the effective paths based on the labels of paths. In the second layer, the effective solution of the above algorithm is considered as the initial solution, and optimal paths are obtained by removing the paths which do not meet the three restrictive conditions in transport time of cargoes, transfer times, and capacity limitation of transport mode. Then, a technique for order preference by similarity to an ideal solution (TOPSIS) was used to calculate integrated weights by combining different cost weights and time weights together, so as to find the optimal paths with the maximum integrated weight value. The result of an application example shows that, compared with the existing labeling algorithm, the proposed algorithm can reduce the search space and avoid generating invalid solutions by including capacity limitation of transport mode; compared with the Lagrangean relaxation method which can only generate the lower and upper bounds on the optimal solution, the proposed algorithm can obtain exact solutions within 30 min, computing time being reduced by about 75%.
-
CHANG T S. Best routes selection in international intermodal networks 王义晶. 联合运输模式及路径优化研究 [J]. Computers and Operations Research, 2008, 35(9): 2877-2891. JANG Y, KIM E. Study on the optimized model of intermodal transport using genetic algorithm FRIEDRICH M. A multi-modal transport model for integrated planning [D]. 北京:北京交通大学,2014. TANG L, HUO J. Multimodal transport distribution network design with time window [J]. Shipping Logistic Research, 2005, 45: 75-98. CARIS A, MACHARIS C, JANSSENS G K. Planning problems in intermodal freight transport: accomplishments and prospects YIPING C, LEI Z, LUNING S. Optimal multi-modal transport model for full loads with time windows MIN H. International intermodal choices via chance constrained goal programming [C]//World Transport Research: Selected Proceedings of the 8th World Conference on Transport Research. Antwerp: World Conference on Transport Research Society, 1999: 1-14. CHO J H, KIM H S, CHOI H R. An intermodal transport network planning algorithm using dynamic programming-a case study: from Busan to Rotterdam in intermodal freight routing [C]//International Conference on Management and Service Science. Wuhan: IEEE, 2011: 1-4. BOARDMAN B S, MALSTROM E M, BUTLER D P, et al. Computer assisted routing of intermodal shipments BOOKBINDER J H, FOX N S. Intermodal routing of Canada Mexico shipments under NAFTA SOUTHWORTH F, PETERSON B E. Intermodal and international freight network modeling [J]. Transportation Planning and Technology, 2008, 31(3): 277-302. MARTINS E Q V. On a multicriteria shortest path problem GANDIBLEUX X, BEUGNIES F, RANDRIAMASY S. Martins' algorithm revisited for multi-objective shortest path problems with a maxmin cost function [C]//2010 International Conference on Logistics Systems and Intelligent Management. Harbin: IEEE, 2010: 147-151. CHANG J O. A generalized decision model for naval weapon procurement: multi-attribute decision making [J]. Transportation Research Part A: Policy and Practice, 1991, 25(6): 351-362. [J]. Applied Intelligence, 2012, 36(3): 529-541. [J]. Computers and Industrial Engineering, 1997, 33(1): 311-314. [J]. Transportation Research Part E: Logistics and Transportation Review, 1998, 34(4): 289-303. [J]. Transportation Research Part C: Emerging Technologies, 2006, 8(1): 147-166. [J]. European Journal of Operational Research, 1984, 16(2): 236-245. [J]. 4OR, 2006, 4(1): 47-59. [D]. Diss: University of South Florida, 2005.
点击查看大图
计量
- 文章访问数: 1025
- HTML全文浏览量: 89
- PDF下载量: 593
- 被引次数: 0