摘要
车辆调度问题(Vehicle Routing Problem,简称为VRP)是物流配送中广泛存在的一类问题,VRP属于强NP问题.在建立了带有时间窗的非满载的VRP问题的数学模型基础上,对启发式算法中的节约算法进行改进,设计出带时间窗的非满载的VRP问题的节约算法.通过对8个客户和13个客户算例的具体计算结果分析该算法的性能,研究表明:节约算法具有易于计算机实现,易于调整,方法易行、效果理想等优点,但在客户规模增加,解的空间增加后,其解的精度也随之下降.
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.
出处
《东北大学学报（自然科学版）》
EI
CAS
CSCD
北大核心
2006年第1期65-68,共4页
Journal of Northeastern University(Natural Science)
基金
辽宁省普通高校优秀青年骨干教师基金资助项目
关键词
车辆调度
节约算法
时间窗
配送路线
vehicle routing
C-W algorithm
time windows
distribution mute.
