实时物流递送路径规划与模拟

吉凌燕等

摘要：近些年来，顾客需求不断多样化、企业竞争更加激烈、全球制造的概念不断发展，不仅我国政府也将物流视为新的经济热点，而且已经引起了全球各个国家的重视。从政府到企业，从中央到地方，都开始物流战略的规划与实施，并且开始物流信息系统的建设。该文以物流路径规划系统为研究对象，介绍了一些著名的最优路径规划算法。在深入分析节约算法的基础上，提出并实现了配合Dijkstra算法的节约里程表算法，开发了以本文算法为核心的实时物流路径规划与模拟系统。

关键词：物流信息系统；车辆路径问题；路径规划；节约里程算法；B2C

中图分类号：TP181 文献标识码：A 文章编号：1009-3044（2014）31-7313-06

Abstract： In recent years， customer needs is growing more different， business competition is becoming more intense， and the concept of global manufacturing continues to develop. Logistics， as a new economic hot spot， has attracted the attention of various countries around the world. From government to business， from the central to local governments， all have begun planning， implementing logistics strategy， and constructing logistics information system.This paper studies path planning of logistics system， analyses existing types of optimal path planning algorithm and compare the advantages and disadvantages of the path planning algorithm. On the basis of in-depth analysis of saving algorithm， this paper proposed and implemented a real-time path planning simulation system with Dijkstra algorithm saves odometer.

Key words： logistics； information systems； vehicle routing； path planning； saving mileage algorithm； B2C

近些年来，顾客需求不断多样化、企业竞争更加激烈、全球制造的概念不断发展，不仅我国政府也将物流视为新的经济热点，而且已经引起了全球各个国家的重视。

早在20世纪60～70年代，发达国家日本、欧美就开始从事和研究物流，不断发展LIS系统，我国的LIS系统还处于企业各自开发，仅供企业内部使用的阶段[1]。

本文以物流路径规划系统为研究对象，分析现有的各类最优路径规划算法，对比了各种路径规划算法的优缺点。在深入分析节约算法的基础上，提出并实现了配合Dijkstra的节约里程表算法的实时路径模拟规划系统。

一般的单车辆路径规划（VRP）是如下定义的：给出一张强连通的复杂图，该图由一组的顶点[V]，一组无向边[E]和一组有向弧[A]组成，并且有子集[V'?V，E'?E，A'?A]并且在边和弧上有非负权值，找到一个包含[V']，[E']，[A']且总权值最小的路线[2]。

在100个结点的前提下，路径规划耗费的计算时间均不超过1.8秒，可见本系统实现算法的高效性和合理性。

4 总结

本文以物流路径规划系统为研究对象，介绍了一些著名的最优路径规划算法，对比了各种路径规划算法的优缺点。在深入分析节约算法的基础上，提出了配合迪杰斯特拉算法的节约里程表算法，然后以此为核心，对实时路径规划模拟系统进行了需求分析，概要设计，详细设计，最终编码实现了实时路径规划模拟系统。

参考文献：

[1] 刘永清，肖忠东，董安邦.基于三层C/S，B/S集成的物流信息系统体系结构的研究[J].湖南科技大学学报：自然科学版，2006，20（3）： 86-9.

[2] LENSTRA J K， KAN A. Complexity of vehicle routing and scheduling problems[J].Networks，1981，11（2）：221-7.

[3] 何莲莲，石峰，周怀北.改进的蚁群算法在2D HP模型中的应用[J].武汉大学学报： 理学版， 2005， 51（1）：33-8.

[4] 宋伟刚，张宏霞，佟玲.有时间窗约束非满载车辆调度问题的节约算法[J].东北大学学报：自然科学版，2006，27（1）： 65-8.