物流配送车辆调度路径优化问题算法研究.doc

物流配送车辆调度路径优化问题算法研究
摘要:近年来,我国物流运行总体平稳,物流需求规模保持较高增幅,物流业增加值平稳增长,但经济运行中的物流成本与其他发达国家相比依然较高。车辆调度配送路径优化问题同时涉及能源消耗和废物的排放问题,随着人们对环境问题给予越来越多的关注,因而其一直是国内外研究的热点。同时物流配送车辆调度问题在企业运营中起着重要的作用。文章首先简介了车辆调度问题,然后从研究的精确算法和启发式算法两方面较为详细地论述了国内外有关车辆调度问题的研究现状,总结了研究中存在的问题,并对物流算法的发展进行了展望。
关键词:车辆调度;路径优化;启发式算法
中图分类号:F253 文献标识码:A

Abstract: In recent years, domestic logistics is developing steady in a whole, the demand of logistics is also in a high amplification. The logistics industry is in a stable increase while the operating cost is still higher than that of developed countries. For that vehicle routing problem both relates to energy consumption and wastage emission
, VRP is a research hotspot at home and abroad under the case that more and more attention are paid to environment protection. Vehicle scheduling holds an important position in enterprise operating. This article first gives a brief description of VRP, then gives a detailed overview of existing algorithms including exact algorithm and heuristic algorithm from home and abroad. Based on the above in formation, this article makes a prospect of algorithms on logistics.
Key words: vehicle scheduling; routing optimization; heuristic algorithm
0 引言
由国家发展和改革委员会、国家统计局和中国物流与采购联合会2014年3月7日联合发布的《2013年全国物流运行情况通报》[1]显示,,%,与GDP的比率为18%。%,%%,。这些数据反映出中国物流成本偏高的现状。,同比增长
%,%。同时,,%。可以看出,全社会物流企业收入增速低于物流费用增速,物流企业普遍盈利能力偏低。报告总结性的指出,2013年,我国物流运行总体平稳,物流需求规模保持较高增幅,物流业增加值平稳增长,但经济运行中的物流成本依然较高。
随着人们对环境问题给予越来越多的关注,关于要求企业保护环境的法律条文相继增加。其中,减少废物的排放量和能源的消耗成为法律规定的两个重要内容。物流作为一个与环境关系密切的行业,车辆调度配送路径优化问题同时涉及能源消耗和废物的排放问题,因而其一直是国内外研究的热点。
综上所述,作为继原材料、劳动力以外的“第三利润源泉”,实现物流合理化具有重要的经济意义与现实意义。一方面,物流配送车辆路径优化有助于企业降低物流成本,提高运作效率,从而增加企业利润。另一方面,通过缓解交通压力,减少资源消耗和对环境的污染真正做到环保物流。
1 车辆调度问题描述
物流配送车辆路径优化问题最早是由线性规划之父Dantzig和Ramser[2]在1959年提出,该问题是交通运输管理、智能救灾调度指挥系统、网络作业调度管理系统、现代物流系统、物流网等应用、研究领域中的基本问题之一,也是最重要的调度问题之一。

配送车辆调度问题要解决的问题[3]是车辆从