同时集散货物的开放式车辆路径问题研究

中国管理科学 ›› 2013, Vol. 21 ›› Issue (4): 187-192.

• 论文 • 上一篇

同时集散货物的开放式车辆路径问题研究

张江华¹, 李进², 高敏刚³

1. 山东大学管理学院, 山东济南 250100;
2. 浙江工商大学信息学院, 浙江杭州 310018;
3. 中国科学院科技政策与管理科学研究所, 北京 100190

收稿日期:2012-07-27 修回日期:2013-04-18 出版日期:2013-08-30 发布日期:2013-08-24
基金资助:
国家自然科学基金资助项目(71201093);山东省优秀中青年科学家科研奖励基金项目(BS2012SF012);教育部人文社科青年项目(12YJC630091);浙江省自然科学基金项目(LQ12G02007);山东大学自主创新基金项目(2012TS194)

Research on the Open Vehicle Routing Problemof with Simultaneous Deliveries and Pickups

ZHANG Jiang-hua¹, LI Jin², GAO Min-Gang³

1. School of Management, Shandong University, Jinan 250100, China;
2. School of Information, Zhejiang Gongshang University, Hangzhou 310018, China;
3. Institute of Policy and Management, Chinese Academy of Sciences, Beijing 100190, China

Received:2012-07-27 Revised:2013-04-18 Online:2013-08-30 Published:2013-08-24

摘要/Abstract

摘要： 本文研究了车辆工作时间限制下同时集散货物的多配送中心开放式车辆路径问题,以车辆数和运输里程最小为目标,建立了多目标规划模型,提出了基于拉格朗日松弛技术和禁忌搜索算法的混合求解算法。该算法首先求出最优解的最大下界,然后采用客户点的分配和调整策略实现解的可行化,其中禁忌搜索引入了4种领域搜索方法,采用了随机变领域搜索方法和重起策略。算例分析表明,该算法能有效地找到满意解,且采用开放式安排路线比闭合式安排路线更加经济合理。

关键词: 车辆路径问题, 同时集散货物, 模型与算法

Abstract: Open vehicle routing problem of multiple distribution centers with simultaneous deliveries and pickups is studied, in which the number and working time of the vehicles are limited. Based on the minimum number and travel distance of vehicles, a multi-objective model is proposed. A novel mixed algorithm based on lagrangian relaxation technique and tabu search algorithm is given, which obtains the maximum lower bound of the optimal solution and then adopts the strategy of assignment and adjustment for clients to achieve the feasible solution. For the tabu search algorithm, a random neighborhood ordering and perturbation mechanisms based on four neighborhood search methods are employed. Computational results show that this algorithm is effective to search the satisfactory solutions and the open collaborative arrangement of vehicle routing is more economic and reasonable than the close independent arrangement of vehicle routing.

Key words: vehicle routing problem, simultaneous deliveries and pickups, model and algorithm

中图分类号:

F505

张江华, 李进, 高敏刚. 同时集散货物的开放式车辆路径问题研究[J]. 中国管理科学, 2013, 21(4): 187-192.

ZHANG Jiang-hua, LI Jin, GAO Min-Gang. Research on the Open Vehicle Routing Problemof with Simultaneous Deliveries and Pickups[J]. Chinese Journal of Management Science, 2013, 21(4): 187-192.

参考文献

[1] Dantzig G, Ramser J. The truck dispathing problem[J]. Management Science, 1959, 6(1): 80-91.
[2] 孟庆春,张江华.基于风险的考虑成本和允许等待的车辆运输调度问题研究[J].中国管理科学, 2009, 17(3):87-92.
[3] 潘震东,唐加福,韩毅.带货物权重的车辆路径问题及遗传算法[J].管理科学学报, 2007, 10(3):23-29.
[4] Erera A L, Morales J C, Savelsbergh M. The vehicle routing problem with stochastic demand and duration constraints[J].Transportation Science,2010,44(4): 474-492.
[5] LiuRan, Jiang Zhibin, Geng Na. A hybrid genetic algorithm for the multi-depot open vehicle routing problem[J]. OR Spectrum, 2012, DOI 10.1007/s00291-012-0289-0.
[6] 李建,达庆利,何瑞银.多车次同时集散货物路线问题研究[J].管理科学学报,2010,13(10):1-7.
[7] 王晓博,李一军.多车型单配送中心混合装卸车辆路径问题研究[J].系统工程学报,2010,25(5):629-636.
[8] Lai Mingyong,Cao Erbao. An improved differential evolution algorithm for vehicle routing problem with simultaneous pickups and deliveries and time windows[J].Engineering Applications of Artificial Intelligence,2010,23(2): 188-195.
[9] Gajpal Y, Abad P. An ant colony system (ACS) for vehicle routing problem with simultaneous delivery and pickup[J]. Computers & Operations Research,2009,36(12): 3215-3223.
[10] Dethloff J. Vehicle routing and reverse logistics: The vehicle routing problem with simultaneous delivery and pick-up[J].OR Spectrum,2001, 23(1): 79-96.
[11] Chen JF,Wu TH. Vehicle routing problem with simultaneous deliveries and pickups[J]. Journal of the Operational Research Society, 2006, 57(5): 579-587.
[12] 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.
[13] Subramanian A, Drummond L M A, Bentes C, Ochi L.S, Farias R. A parallel heuristic for the Vehicle Routing Problem with Simultaneous Pickup and Delivery[J]. Computers & Operations Research, 2010,37(11): 1899-1911.
[14] Mole R, Jameson S. A sequential route-building algorithm employing a generalised savings criterion[J]. Journal of the Operational Research Society,1976, 27(2): 503-511.
[15] Potvin J Y, Rousseau J M. An exchange heruistic for routing problems with time windows[J]. Journal of the Operational Research Society,1995,46(12):1433-1446.

同时集散货物的开放式车辆路径问题研究

Research on the Open Vehicle Routing Problemof with Simultaneous Deliveries and Pickups

PDF (PC)

可视化

被引次数

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 13

Metrics

本文评价

推荐阅读 10

[1]	郭放, 杨珺, 杨超. 考虑差异化服务时间的多车型电动汽车路径优化与充电策略研究[J]. 中国管理科学, 2019, 27(8): 118-128.
[2]	方文婷, 艾时钟, 王晴, 范君博. 基于混合蚁群算法的冷链物流配送路径优化研究[J]. 中国管理科学, 2019, 27(11): 107-115.
[3]	潘雯雯, 郭海湘, 杜天松, 刘晓, 王德运. 油套管回收车辆路径问题及基于清除小生境差分演化求解算法研究[J]. 中国管理科学, 2018, 26(5): 118-128.
[4]	王晶, 刘昊天, 黄钧. 考虑伤情分类的灾后创伤伤员救治与转运路径优化研究[J]. 中国管理科学, 2017, 25(8): 114-122.
[5]	颜瑞, 朱晓宁, 张群, 戚耀元, 蔺俞铮. 考虑二维装箱约束的多车场带时间窗的车辆路径问题模型及算法研究[J]. 中国管理科学, 2017, 25(7): 67-77.
[6]	符卓, 刘文, 邱萌. 带软时间窗的需求依订单拆分车辆路径问题及其禁忌搜索算法[J]. 中国管理科学, 2017, 25(5): 78-86.
[7]	刘艳秋, 徐世达, 张颖, 李佳. 考虑路径可行性与仓储集货模式下的回收车辆路径问题研究[J]. 中国管理科学, 2016, 24(12): 98-107.
[8]	李进, 傅培华, 李修琳, 张江华, 朱道立. 低碳环境下的车辆路径问题及禁忌搜索算法研究[J]. 中国管理科学, 2015, 23(10): 98-106.
[9]	张群, 颜瑞. 基于改进模糊遗传算法的混合车辆路径问题 [J]. 中国管理科学, 2012, (2): 121-128.
[10]	王征, 张俊, 王旭坪. 多车场带时间窗车辆路径问题的变邻域搜索算法[J]. 中国管理科学, 2011, 19(2): 99-109.
[11]	余明珠, 李建斌, 雷东. 装卸一体化的车辆路径问题及基于插入法的新禁忌算法[J]. 中国管理科学, 2010, 18(2): 89-95.
[12]	侯立文, 谭家美, 赵元. 求解带时间窗的客户需求可分条件下的车辆路径问题[J]. 中国管理科学, 2007, 15(6): 46-51.
[13]	陆琳, 谭清美. 基于自感应蚁群算法的VRPSDP问题研究[J]. 中国管理科学, 2007, 15(2): 97-103.