實時物流遞送路徑規劃與模擬

吉凌燕等

摘要：近些年來，顧客需求不斷多樣化、企業競爭更加激烈、全球制造的概念不斷發展，不僅我國政府也將物流視為新的經濟熱點，而且已經引起了全球各個國家的重視。從政府到企業，從中央到地方，都開始物流戰略的規劃與實施，并且開始物流信息系統的建設。該文以物流路徑規劃系統為研究對象，介紹了一些著名的最優路徑規劃算法。在深入分析節約算法的基礎上，提出并實現了配合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]。……