交通运输系统工程与信息

交通运输系统工程与信息 ›› 2006, Vol. 6 ›› Issue (4): 75-80 .

• 系统工程理论与方法 • 上一篇    下一篇

随机车辆路径问题的模型及其算法

杨信丰1，杨庆丰2   

  1. 1.兰州交通大学 交通运输学院，兰州730070； 2.河南建筑职工大学，郑州450007
  • 收稿日期:2006-03-05 修回日期:1900-01-01 出版日期:2006-08-20 发布日期:2006-08-20

Model and Algorithm of Vehicle Routing Problem with Stochastic Travel Time

YANG Xin-feng1，YANG Qing-feng2   

  1. 1.School of traffic & Transportation Engineering, Lanzhou Jiaotong University, Lanzhou 730070, China; 2. Henan Architecture Engineering School, Zhengzhou 450007，China
  • Received:2006-03-05 Revised:1900-01-01 Online:2006-08-20 Published:2006-08-20

PDF

被引次数

43

摘要： 在物流活动的商品配送运输中，由于受不确定因素的干扰，对配送车辆调度的适时性造成了很大影响，从而增加了配送成本和降低了配送的服务质量。本文考虑客户对配送时间的要求和车辆行驶时间的不确定性，建立了以车辆配送总行驶距离最小化为目标的机会约束规划模型，并构造了求解该模型的单亲遗传算法，通过实例对模型求解，结果表明，该算法是很有效的。

关键词: 车辆路径问题, 随机车辆路径, 机会约束模型, 遗传算法

Abstract: Realisticaly, the uncertain factors have great effect on vehicle scheduling in the commodity delivery. Those factors have always made the delivery cost increased and the delivery quality declined. This paper sets up a stochastic chance-controled programming model to minimize total vehicle traveling distance and forms a single genetic algorithm for the model while considering customers’ requests about delivery time and uncertainty of traveling time. The simulation results show that the algorithm is very efficient. So there is both theoretical and practical value while taking design and realization of distribution vehicle routing problem as its study objects.

Key words: vehicle routing problem, stochastic vehicle routing, chance-constrained programming model, genetic algorithm