考虑均衡性的不确定时间车辆调度问题研究

运筹与管理 ›› 2013, Vol. 22 ›› Issue (2): 86-91.

考虑均衡性的不确定时间车辆调度问题研究

任锡德¹, 朱建明¹, 王晶², 黄钧¹

1.中国科学院大学,北京 100049;
2.北京工商大学商学院,北京 100048

收稿日期:2011-09-23 出版日期:2013-04-25
基金资助:
国家自然科学基金“非常规突发事件应急管理研究”重大研究计划培育项目(90924008),国家自然科学基金青年基金项目(71001099);中国科学院研究生院院长基金

Research on Load-balancing Vehicle Routing Problem with Uncertain Travel Time

REN Xi-de¹, ZHU Jian-ming¹, WANG Jing², HUANG Jun¹

1. University of Chinese Academy of Sciences, Beijing 100049, China;
2. School of Business, Beijing Technology and Business University, Beijing 100048, China

Received:2011-09-23 Online:2013-04-25

摘要/Abstract

摘要： 本文针对车辆调度实际运行过程中时间的不确定性问题,提出了包含时间窗口、车辆容量约束的配送服务线路随机规划模型,以最小化调用的车辆数目和运行距离,降低顾客的不满意度并且尽可能保证每条路线的均衡性。结合模型,给出了基于禁忌搜索的混合启发式算法,并且生成多个算例,依据算例结果说明模型和算法优越性,同时说明可以在不降低顾客满意度和不提高总运输成本的基础上,降低各条线路之间的时间差异。

关键词: 运筹学, 时间窗口, 随机规划, 路线时间方差, 禁忌搜索, 不确定时间, 车辆路线

Abstract: The travel time of vehicles is always stochastic. In view of this, a stochastic programming model including time-window and vehicle capacity constraints is given to minimize the number of vehicles, traveling distance, the dissatisfaction of costumers, and the time variance of different routes at the same time. A heuristic algorithm based on tabu search is raised to solve the model, and several cases are generated to prove the efficiency of the algorithm. And the computation result shows that the time-variance of different routes can be optimized without increasing the cost or decreasing the service quality of costumers.

Key words: operations research, time-windows, stochastic programming, tabu-search, uncertain travel-time, load balancing, VRP

中图分类号:

O224
C931

任锡德, 朱建明, 王晶, 黄钧. 考虑均衡性的不确定时间车辆调度问题研究[J]. 运筹与管理, 2013, 22(2): 86-91.

REN Xi-de, ZHU Jian-ming, WANG Jing, HUANG Jun. Research on Load-balancing Vehicle Routing Problem with Uncertain Travel Time[J]. Operations Research and Management Science, 2013, 22(2): 86-91.

参考文献

[1] Guo Yaohuang, Xie Binglei, Guo Qiang. Overview of stochastic vehicle routing problems[J]. Journal of Southeast Jiaotong University, 2002, 10(2): 113-121
[2] Burak Eksioglu, Afif Volkan Vural, Arnold Reisman. The vehicle routing problems: a taxonomic review[J]. Computers and Industrial Engineering, 2009, 57: 1472-1483
[3] Huey-Kuo Chen,Che-Fu Hsueh, Mei-Shiang Chang. The real-time time-dependent vehicle routing problem[J]. Transportation Research Part E, 2006, 42: 383-408
[4] Jean-Yves Potvina. Vehicle routing and scheduling with dynamic travel times[J]. Computers and operations research, 2006, 33: 1129-1137
[5] Chaug-Ing Hsu. Vehicle routing problem with time-windows for perishable food delivery[J]. Journal of Food Engineering, 2007, 80 :465-475
[6] P.P. Repoussis. Solving the fleet size and mix vehicle routing problem with time windows via adaptive memory programming[J]. Transportation Research Part C(2009) , doi:10.1016/j.trc, 2009-08-04
[7] Roberto Cordone, Roberto Wolfer calvo. A heuristic for the vehicle routing problem with time windows[J]. Journal of Heuristics, 2001, 7: 107-129
[8] Li Xiangyong. Vehicle routing problems with time windows and stochastic travel and service times: Models and algorithm[J]. Int.J Production Economics, 2010, 125: 137-145
[9] Gendreau M, Hertz A, Laporte G. A tabu search heuristic for the vehicle routing problem[J]. Management Science, 1994, 40(10), 12: 76-1290.
[10] Clarke G, Wright J R. Scheduling of vehicle routing problem from a central depot to a number of delivery points[J]. OperationsResearch, 1964, 12: 568-581.
[11] Solomon MM. Real-time vehicle routing problem with time windows[J]. European Journal of Operational Research, 2009, 194: 711-727
[12] 蔡临宁.物流系统规划-建模及实例分析[M].机械工业出版社,2003.9.

[1]	陈煜婷, 张惠珍. 双层级医疗设施选址问题及禁忌搜索算法[J]. 运筹与管理, 2021, 30(9): 56-63.
[2]	尉迟群丽, 何正文, 王能民. 考虑缺货的闭环供应链选址-库存-路径集成优化[J]. 运筹与管理, 2021, 30(2): 53-60.
[3]	宁敏静, 郑小强, 何正文. 基于随机活动工期的现金流动态均衡前摄性与反应性项目调度优化[J]. 运筹与管理, 2021, 30(2): 117-123.
[4]	王艳婷, 何正文, 和媛媛. 随机环境下基于成本经济的项目调度权衡优化研究[J]. 运筹与管理, 2021, 30(12): 20-27.
[5]	胡雪君, 王建江, 谭跃进, 徐培德, 崔南方. 带有资源转移时间的RCPSP资源流模型及算法[J]. 运筹与管理, 2021, 30(12): 42-50.
[6]	薛桂琴, 王征. 带客户协同分仓的动态车辆路径问题研究[J]. 运筹与管理, 2021, 30(11): 19-25.
[7]	李文莉, 李昆鹏, 阮文意. 轴辐式同城快递网络模式研究[J]. 运筹与管理, 2020, 29(4): 36-42.
[8]	汪洪涛, 张翔, 王珂. 1996~2017年《Operations Research》期刊发文统计分析[J]. 运筹与管理, 2020, 29(2): 229-239.
[9]	项寅. 恐怖分子入侵阻止网络的双层规划建模与禁忌搜索分析[J]. 运筹与管理, 2020, 29(10): 1-10.
[10]	王诺, 丁凯, 吴迪, 吴暖. 面向远海岛礁群的双向物流网络规划[J]. 运筹与管理, 2019, 28(6): 118-128.
[11]	贺冰倩, 李昆鹏, 成幸幸. 快递企业“最后一公里”快件收派优化方案研究[J]. 运筹与管理, 2019, 28(1): 27-34.
[12]	徐国勋, 李妍峰, 李军, 徐冠宇. 多类型公共自行车调运问题[J]. 运筹与管理, 2019, 28(1): 116-124.
[13]	陈江涛, 吕建秋. 基于知识图谱的运筹学发展现状及趋势研究[J]. 运筹与管理, 2019, 28(1): 194-199.
[14]	张萌,王能民. 重大事故规避的危险品运输车辆路径优化研究[J]. 运筹与管理, 2018, 27(8): 1-9.
[15]	高沛然, 张金隆, 艾学轶, 李明, 马自香. PLS-DEMATEL方法及其应用研究——以组织敏捷性的IT影响因素分析为例[J]. 运筹与管理, 2018, 27(3): 126-132.