货滚码头甩挂运输系统内牵引车调度优化
|
摘要
作业舱容限制与多船同步作业是导致货滚甩挂码头牵引车调度困难的关键原因.为提高牵引车的运作效率,降低系统运营成本,建立了货滚甩挂码头牵引车调度的混合整数规划模型,推导了目标函数的下界值.同时,开发模拟退火算法,求解滚装船在港时间无交叉和有交叉两大类算例.结果显示,模拟退火算法所得方案可大幅度降低现有调度规则下的运营成本,同时与下界值的差距较小,证明了模型和算法的有效性.而且,当滚装船在港时间无交叉时算法的优化效果更好.
The constraint of cabin capacity and the synchronized operation of multi ships are key factors to complicated scheduling of tractors at the ro-ro tractor-and-trailer terminal. To improve the operation efficiency of tractors and reduce the operating cost of the ro-ro terminal as a whole, this paper establishes a mixed integer programming model for the tractor scheduling. A lower bound of the objective function is derived. By adopting the simulated annealing algorithm(SA), numerical solutions are obtained under two conditions: overlapping ship turnaround time and non-overlapping ship turnaround time. Results show that the operating cost obtained by SA is much lower than the cost of the practical operation rule. Also, the gap between the numerical results and the lower bound is small, which further proves the effectiveness of the model and the algorithm. Moreover,the algorithm performs better when the ships' turnaround time has no overlap.
The constraint of cabin capacity and the synchronized operation of multi ships are key factors to complicated scheduling of tractors at the ro-ro tractor-and-trailer terminal. To improve the operation efficiency of tractors and reduce the operating cost of the ro-ro terminal as a whole, this paper establishes a mixed integer programming model for the tractor scheduling. A lower bound of the objective function is derived. By adopting the simulated annealing algorithm(SA), numerical solutions are obtained under two conditions: overlapping ship turnaround time and non-overlapping ship turnaround time. Results show that the operating cost obtained by SA is much lower than the cost of the practical operation rule. Also, the gap between the numerical results and the lower bound is small, which further proves the effectiveness of the model and the algorithm. Moreover,the algorithm performs better when the ships' turnaround time has no overlap.
引文
[1]吕延昌.鲁辽滚装船甩挂运输的业务流程设计.物流技术,2014,33(9):36-38.Lv Y C.Design of business process of ro-ro drop&pull transportation in Shandong-Liaoning region.Logistics Technology,2014,33(9):36-38.(in Chinese)
[2]Chao I.A tabu search method for the truck and trailer routing problem.Computers&Operations Research,2002,29(1):33-51.
[3]Lin S,Yu V F,Chou S.Solving the truck and trailer routing problem based on a simulated annealing heuristic.Computers&Operations Research,2009,36(5):1683-1692.
[4]Lin S,Yu V F,Chou S.A note on the truck and trailer routing problem.Expert Systems with Applications,2010,37(1):899-903.
[5]Lin S,Yu V F,Lu C.A simulated annealing heuristic for the truck and trailer routing problem with time windows.Expert Systems with Applications,2011,38(12):15244-15252.
[6]Villegas J G,Prins C,Prodhon C,et al.A GRASP with evolutionary path relinking for the truck and trailer routing problem.Computers&Operations Research,2011,38(9):1319-1334.
[7]Villegas J G,Prins C,Prodhon C,et al.A matheuristic for the truck and trailer routing problem.European Journal of Operational Research,2013,230(2):231-244.
[8]Derigs U,Pullmann M,Vogel U.Truck and trailer routing-problems,heuristics and computational experience.Computers&Operations Research,2013,40(2):536-546.
[9]胡志华,陶莎.基于混合进化算法的甩挂配送问题.公路交通科技,2013,30(5):147-152.Hu Z H,Tao S.Distribution by trailer pick-up transport based on hybrid evolutionary algorithm.Journal of Highway and Transportation Research and Development,2013,30(5):147-152.(in Chinese)
[10]Tan K C,Chew Y H,Lee L H.A hybrid multi-objective evolutionary algorithm for solving truck and trailer vehicle routing problems.European Journal of Operational Research,2006,172:855-885.
[11]Lee L H,Tan K C,Ou K,et al.Vehicle capacity planning system:A case study on vehicle routing problem with time windows.Ieee Transactions on Systems Man and Cybernetics Part A-Systems and Humans,2003,33(2):169-178.
[12]Francis P,Zhang G,Smilowitz K.Improved modeling and solution methods for the multi-resource routing problem.European Journal of Operational Research,2007,180(3):1045-1059.
[13]Xue Z,Zhang C,Lin W,et al.A tabu search heuristic for the local container drayage problem under a new operation mode.Transportation Research Part E-Logistics and Transportation Review,2014,62:136-150.
[14]Xue Z,Lin W,Miao L,et al.Local container drayage problem with tractor and trailer operating in separable mode.Flexible Services and Manufacturing Journal,2015,27(2-3):431-450.
[15]Xue Z,Zhang C,Yang P,et al.A combinatorial benders’cuts algorithm for the local container drayage problem.Mathematical Problems in Engineering,2015(2015):1-7.
[16]胡志华,曹杨,王云霞.集装箱集散的空重箱循环甩挂调度方法.武汉理工大学学报,2012,34(10):68-73.Hu Z H,Cao Y,Wang Y X.Cyclic tractor-and-trailer scheduling for consolidation and distribution of loaded and empty containers.Journal of Wuhan University of Technology,2012,34(10):68-73.(in Chinese)
[17]胡志华.集装箱码头间互拖的集卡甩挂运输调度问题.重庆交通大学学报(自然科学版),2013,32(2):313-317.Hu Z H.Scheduling of container truck-and-trailer transport between two ports.Journal of Chongqing Jiaotong University(Natural Science),2013,32(2):313-317.(in Chinese)
[18]钟慧玲,吴聪,张冠湘,等.内河港口甩挂运输组织中场站选址问题研究.交通运输系统工程与信息,2013,13(3):126-131.Zhong H L,Wu C,Zhang G X,et al.Freight station location of inland port semi-trailer swap transport organization.Journal of Transportation System Engineering and Information Technology,2013,13(3):126-131.(in Chinese)
[19]余莉,林桦,陈伯如.网络型甩挂运输模式下的车辆调度问题.交通运输工程与信息学报,2014,12(2):58-64.Yu L,Lin H,Chen B R.Research of vehicle scheduling problem of the network drop and pull transport.Journal of Transportation Engineering and Information,2014,12(2):58-64.(in Chinese)
[20]侯玉梅,贾震环,田歆,等.带软时间窗整车物流配送路径优化研究.系统工程学报,2015,30(2):240-250.Hou Y M,Jia Z H,Tian X,et al.Research on the optimization on the vehicle logistics distribution with soft time windows.Journal of Systems Engineering,2015,30(2):240-250.(in Chinese)
[2]Chao I.A tabu search method for the truck and trailer routing problem.Computers&Operations Research,2002,29(1):33-51.
[3]Lin S,Yu V F,Chou S.Solving the truck and trailer routing problem based on a simulated annealing heuristic.Computers&Operations Research,2009,36(5):1683-1692.
[4]Lin S,Yu V F,Chou S.A note on the truck and trailer routing problem.Expert Systems with Applications,2010,37(1):899-903.
[5]Lin S,Yu V F,Lu C.A simulated annealing heuristic for the truck and trailer routing problem with time windows.Expert Systems with Applications,2011,38(12):15244-15252.
[6]Villegas J G,Prins C,Prodhon C,et al.A GRASP with evolutionary path relinking for the truck and trailer routing problem.Computers&Operations Research,2011,38(9):1319-1334.
[7]Villegas J G,Prins C,Prodhon C,et al.A matheuristic for the truck and trailer routing problem.European Journal of Operational Research,2013,230(2):231-244.
[8]Derigs U,Pullmann M,Vogel U.Truck and trailer routing-problems,heuristics and computational experience.Computers&Operations Research,2013,40(2):536-546.
[9]胡志华,陶莎.基于混合进化算法的甩挂配送问题.公路交通科技,2013,30(5):147-152.Hu Z H,Tao S.Distribution by trailer pick-up transport based on hybrid evolutionary algorithm.Journal of Highway and Transportation Research and Development,2013,30(5):147-152.(in Chinese)
[10]Tan K C,Chew Y H,Lee L H.A hybrid multi-objective evolutionary algorithm for solving truck and trailer vehicle routing problems.European Journal of Operational Research,2006,172:855-885.
[11]Lee L H,Tan K C,Ou K,et al.Vehicle capacity planning system:A case study on vehicle routing problem with time windows.Ieee Transactions on Systems Man and Cybernetics Part A-Systems and Humans,2003,33(2):169-178.
[12]Francis P,Zhang G,Smilowitz K.Improved modeling and solution methods for the multi-resource routing problem.European Journal of Operational Research,2007,180(3):1045-1059.
[13]Xue Z,Zhang C,Lin W,et al.A tabu search heuristic for the local container drayage problem under a new operation mode.Transportation Research Part E-Logistics and Transportation Review,2014,62:136-150.
[14]Xue Z,Lin W,Miao L,et al.Local container drayage problem with tractor and trailer operating in separable mode.Flexible Services and Manufacturing Journal,2015,27(2-3):431-450.
[15]Xue Z,Zhang C,Yang P,et al.A combinatorial benders’cuts algorithm for the local container drayage problem.Mathematical Problems in Engineering,2015(2015):1-7.
[16]胡志华,曹杨,王云霞.集装箱集散的空重箱循环甩挂调度方法.武汉理工大学学报,2012,34(10):68-73.Hu Z H,Cao Y,Wang Y X.Cyclic tractor-and-trailer scheduling for consolidation and distribution of loaded and empty containers.Journal of Wuhan University of Technology,2012,34(10):68-73.(in Chinese)
[17]胡志华.集装箱码头间互拖的集卡甩挂运输调度问题.重庆交通大学学报(自然科学版),2013,32(2):313-317.Hu Z H.Scheduling of container truck-and-trailer transport between two ports.Journal of Chongqing Jiaotong University(Natural Science),2013,32(2):313-317.(in Chinese)
[18]钟慧玲,吴聪,张冠湘,等.内河港口甩挂运输组织中场站选址问题研究.交通运输系统工程与信息,2013,13(3):126-131.Zhong H L,Wu C,Zhang G X,et al.Freight station location of inland port semi-trailer swap transport organization.Journal of Transportation System Engineering and Information Technology,2013,13(3):126-131.(in Chinese)
[19]余莉,林桦,陈伯如.网络型甩挂运输模式下的车辆调度问题.交通运输工程与信息学报,2014,12(2):58-64.Yu L,Lin H,Chen B R.Research of vehicle scheduling problem of the network drop and pull transport.Journal of Transportation Engineering and Information,2014,12(2):58-64.(in Chinese)
[20]侯玉梅,贾震环,田歆,等.带软时间窗整车物流配送路径优化研究.系统工程学报,2015,30(2):240-250.Hou Y M,Jia Z H,Tian X,et al.Research on the optimization on the vehicle logistics distribution with soft time windows.Journal of Systems Engineering,2015,30(2):240-250.(in Chinese)