大规模同时集散货物路线问题的新禁忌搜索算法设计

基金项目:

国家自然科学基金资助项目(70772059)

江苏省农机局基金资助项目(GXZ08002)

详细信息

作者简介:
李建(1979- ),男,讲师,研究方向为物流系统优化,E-mail:telorance@126.com

计量
- 文章访问数:1535
- HTML全文浏览量:131
- PDF下载量:106
- 被引次数:0
出版历程
- 收稿日期:2008-11-10

New Tabu Search Algorithm for Large-Scale Vehicle Routing Problem with Simultaneous Deliveries and Pickups

摘要

摘要:提出了一种新的禁忌搜索算法.该方法集成大量的邻域搜索方法,采用基于线路集合的分解策略,以及重起和扰动策略,将当前解分解成几个独立的路线子集合,用禁忌搜索法求解每个路线子集合,再将求得的子集合最好路线组成新的当前解.与记录更新法和传统禁忌搜索算法的最好目标值相比,在14组测试数据中,取得8个新的最好目标值,其余的误差值不超过2.41%,且有2组数据的车辆数减少了1辆.
- 车辆路线问题/
- 多邻域搜索/
- 禁忌搜索/
- 重起/
- 扰动
Abstract:A new tabu search algorithm that integrates many neighborhood search methods,and adopts route set-based decomposition,restart and perturbation strategies,was proposed.The current solution is divided into several subsets of routes,each of which is solved by the tabu search algorithm and the best solutions of the subsets are then merged to form a new current solution.Computational results show that compared with record-to-record travel and traditional tabu search algorithm,the new tabu search algorithm can improve on 8 out of 14 of the best known solutions and reduce the number of vehicles by one in 2 cases,with error less than 2.41% for the others.
- vehicle routing problem/
- multiple neighborhoods search/
- tabu search/
- restart/
- perturbation

HTML全文

参考文献 (12)

MIN H.The multiple vehicle routing problem with simultaneous delivery and pickup points[J].Transportation Research A,1989,23(4):377-386.

TANG F A,GALVO R D.A tabu search algorithm for the vehicle routing problems with simultaneous pickup and delivery service[J].Computers Operations Research,2006,33(3):595-619.

NAGY G,SALHI S.Heuristic algorithms for single and multiple depot vehicle routing problems with pickups and deliveries[J].European Journal of Operational Research,2005,162(1):126-141.

郎茂祥.装卸混合车辆路径问题的模拟退火算法研究[J].系统工程学报,2005,20(5):485-491.LANG Maoxiang.Study on simulated annealing algorithm for vehicle routing problem with backhauls[J].Journal of systems engineering,2005,20(5):485-491.

张建勇,李军.具有同时配送和回收需求的车辆路径问题的混合遗传算法[J].中国公路学报,2006,19(4):118-122.ZHANG Jianyong,LI Jun.Hybrid genetic algorithm to vehicle routing problem with simultaneous delivery and pick-up[J].China Journal of Highway and Transport,2006,19(4):118-122.

曲志伟,蔡临宁,李晨,等.大规模车辆配送/收集问题的求解框架[J].清华大学学报(自然科学版),2004,44(5):581-584.QU Zhiwei,CAI Linning,LI Chen,et al.Solution framework for the large scale vehicle delivery/collection problem[J].Journal of Tsinghua University(Science and Technology),2004,44(5):581-584.

SALHI S,NAGY G.A cluster insertion heuristic for single and multiple depot vehicle routing problems with backhauling[J].Journal of the Operational Research Society,1999,50(10):1034-1042.

DETHLOFF J.Vehicle routing and reverse logistics:the vehicle routing problem with simultaneous delivery and pick-up[J].OR Spektrum,2001,23(1):79 96.

CHEN J F,WU T H.Vehicle routing problem with simultaneous deliveries and pickups[J].Journal of the Operational Research Society,2006,57(5):579-587.

李建,张永.一类集散货物路线问题的禁忌搜索算法设计[J].系统工程理论与实践,2007,27(6):117-123.LI Jian,ZHANG Yong.A tabu search algorithm for vehicle routing problem with simultaneous deliveries and pickups[J].Systems Engineering-Theory Practice,2007,27(6):117-123.

DERIGS U,KAISER R.Applying the attribute based hill climber heuristic to the vehicle routing problem[J].European Journal of Operational Research,2007,177(2):719-732.

CHRISTOFIDES N,MINGOZZI A,TOTH P,et al.Combinatorial optimization[M].Chichester:Wiley,1979:315-338.

施引文献

附加材料 (0)

访问统计

点击查看大图

计量

文章访问数:1535
HTML全文浏览量:131
PDF下载量:106
被引次数:0