东北大学学报（自然科学版）

东北大学学报(自然科学版) ›› 2006, Vol. 27 ›› Issue (1): 65-68.DOI: -

• 论著 • 上一篇    下一篇

有时间窗约束非满载车辆调度问题的节约算法

宋伟刚;张宏霞;佟玲;   

  1. 东北大学机械工程与自动化学院;东北大学机械工程与自动化学院;东北大学机械工程与自动化学院 辽宁沈阳110004;辽宁沈阳110004;辽宁沈阳110004
  • 收稿日期:2013-06-23 修回日期:2013-06-23 出版日期:2006-01-15 发布日期:2013-06-23
  • 通讯作者: Song, W.-G.
  • 作者简介:-
  • 基金资助:
    辽宁省普通高校优秀青年骨干教师基金资助项目

C-W algorithm for vehicle routing problem of non-full loads with time windows

Song, Wei-Gang (1); Zhang, Hong-Xia (1); Tong, Ling (1)   

  1. (1) School of Mechanical Engineering and Automation, Northeastern University, Shenyang 110004, China
  • Received:2013-06-23 Revised:2013-06-23 Online:2006-01-15 Published:2013-06-23
  • Contact: Song, W.-G.
  • About author:-
  • Supported by:
    -

RichHTML

1

PDF (PC)

1938

摘要： 车辆调度问题(Vehicle Routing Problem,简称为VRP)是物流配送中广泛存在的一类问题,VRP属于强NP问题.在建立了带有时间窗的非满载的VRP问题的数学模型基础上,对启发式算法中的节约算法进行改进,设计出带时间窗的非满载的VRP问题的节约算法.通过对8个客户和13个客户算例的具体计算结果分析该算法的性能,研究表明:节约算法具有易于计算机实现,易于调整,方法易行、效果理想等优点,但在客户规模增加,解的空间增加后,其解的精度也随之下降.

关键词: 车辆调度, 节约算法, 时间窗, 配送路线

Abstract: Vehicle Routing Problem (VRP) as a common problem in the logistics distribution is also a typical NP-hard problem. On the basis of developing a mathematic model for VRP of non-full loads with time windows, the C-W (Clark-Wright) algorithm used in heuristic algorithm is improved with a new C-W algorithm proposed for the VRP of non-full loads with time windows. The performance of this algorithm is analyzed through two different computational examples involving 8 customers and 13 customers. The results showed the new C-W algorithm is easy to implement and readjust on computers with ideal computational results available. However, the precision of the solution will be reduced if the number of customers increases with increasing solution spaces.

中图分类号: