Dynasearch Algorithms for Solving Time Dependent Traveling Salesman Problem
-
摘要: 为解决基于时段的时间依赖型旅行商问题(time-dependent traveling salesman problem,TDTSP),提出处理跨时段的方法,并建立了相应的数学模型.用动态搜索算法ds-k-opt(k=2,2.5,3)分别求解该问题.仿真算例表明,动态搜索算法中部分ds-2.5-opt解和绝大部分ds-3-opt解优于动态规划启发式算法,且能求解更大规模的TDTSP问题.动态搜索算法的解随k的增大而更优,但运算时间也更长.Abstract: A method was proposed to solve the time-dependent traveling salesman problem(TDTSP) happening in more than one time period,and its model was derived.The model was solved with dynasearch algorithms,ds-k-opt(k=2,2.5,3).Simulation results show that some of the ds-2-opt solutions and most of ds-3-opt solutions are better than those of dynamic programming heuristics,and the dynasearch algorithms can solve a TDTSP with a larger scale.With an increase in k,solutions become better,while the computation time becomes longer.
-
MALANDRAKI C.Time dependent vehicle routing problem:formulations,solution algorithms and computations experiments[D].Evanston:Northwestern University,1989.[2] AHN B H,SHIN J Y.Vehicle-routing with time windows and time-varying congestion[J].Journal of the Operational Research Society,1991,42(5):393-400.[3] HILL A V,BENTON W C.Modeling intra-city time-dependent travel speeds for vehicle scheduling problems[J].Journal of the Operational Research Society,1992,43(4):343-351.[4] MALANDRAKI C,DASKIN M S.Time dependent vehicle routing problems:Formulations,properties and heuristic algorithms[J].Transportation Science,1992,26(3):185-200.[5] MALANDRAKI C,DIAL R B.A restricted dynamic programming heuristic algorithm for the time dependent traveling salesman problem[J].European Journal of Operational Research,1996,90(1):45-55.[6] HORN M E T.Efficieut modeling of travel in networks with time-varying link speeds[J].Networks,2000,36 (2):80-90.[7] ICHOUA S,GENDREAU M,POTVIN J Y.Vehicle dispatching with time-dependent travel times[J].European Journal of Operational Research,2003,144(2):379-396.[8] FLEISCHMANN B,GIETZ M,GNUTZMANN S.Time-varying travel times in vehicle routing[J].Transportation Science,2004,38(2):160-173.[9] HAGHANI A,JUNG S.A dynamic vehicle routing problem with time-dependent travel times[J].Computer & Operations Research,2005,32(11):2 959-2 986.[10] LI F Y.Modeling and solving variants of the vehicle routing problem:algorithms,test problems,and computational results[D].Baltimore:University of Maryland,2005.[11] PICARD J C,QUERYRANNE M.The time-dependent traveling salesman problem and its application to the tardiness problem in one-machine scheduling[J].Operations Research,1978,26 (1):86-110.[12] FOX K R,GAVISH B,GRAVES S C.A n-constraint formulation of the (time-dependent) traveling salesman problem[J].Operations Research,1980,28(4):1 018-1 021.[13] LUCENA A.Time-dependent traveling salesman problem-the deliveryman case[J].Networks,1990,20(66):753-763.[14] BIANCO L,MINGOZZI A,RICCIARDELLI S.The traveling salesman problem with cumulative cost[J].Networks,1993,23(2):81-91.[15] WIEL R J V,SAHINIDIS N V.Heuristic bounds and test problem generation for the time-dependent traveling salesman problem[J].Transportation Science,1995,29(22):167-183.[16] CONGRAM R K.Polynominally searchable exponential neighborhoods for sequencing problems in combinatorial optimization[D].Southampton:University of Southampton,2000.[17] LIN S,KERNIGHAN B.An effective heuristic algorithm for the traveling salesman problem[J].Operations Research,1973,21(2):498-516.[18] OR I.Traveling salesman-type combinatorial problems and their relation to the logistics of blood banking[D].Evanston:Northwestern University,1976.
点击查看大图
计量
- 文章访问数: 1516
- HTML全文浏览量: 79
- PDF下载量: 416
- 被引次数: 0