• ISSN 0258-2724
  • CN 51-1277/U
  • EI Compendex
  • Scopus 收录
  • 全国中文核心期刊
  • 中国科技论文统计源期刊
  • 中国科学引文数据库来源期刊

用动态搜索算法求解时间依赖型旅行商问题

李妍峰 李军 赵达

李妍峰, 李军, 赵达. 用动态搜索算法求解时间依赖型旅行商问题[J]. 西南交通大学学报, 2008, 21(2): 187-193.
引用本文: 李妍峰, 李军, 赵达. 用动态搜索算法求解时间依赖型旅行商问题[J]. 西南交通大学学报, 2008, 21(2): 187-193.
LI Yanfeng, LI Jun, ZHAO Da. Dynasearch Algorithms for Solving Time Dependent Traveling Salesman Problem[J]. Journal of Southwest Jiaotong University, 2008, 21(2): 187-193.
Citation: LI Yanfeng, LI Jun, ZHAO Da. Dynasearch Algorithms for Solving Time Dependent Traveling Salesman Problem[J]. Journal of Southwest Jiaotong University, 2008, 21(2): 187-193.

用动态搜索算法求解时间依赖型旅行商问题

基金项目: 

国家社会科学基金资助项目(07BJY038)

教育部新世纪优秀人才支持计划项目(NCET-04-0886)

四川省教育厅青年基金项目(2005B025)

详细信息
    作者简介:

    李妍峰(1980- ),女,讲师,博士研究生,研究方向为物流优化,E-mail:yanwaa@126.com

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的增大而更优,但运算时间也更长.

     

  • 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
出版历程
  • 收稿日期:  2007-05-09
  • 刊出日期:  2008-04-25

目录

    /

    返回文章
    返回