實(shí)時(shí)物流遞送路徑規(guī)劃與模擬

吉凌燕等

摘要：近些年來(lái)，顧客需求不斷多樣化、企業(yè)競(jìng)爭(zhēng)更加激烈、全球制造的概念不斷發(fā)展，不僅我國(guó)政府也將物流視為新的經(jīng)濟(jì)熱點(diǎn)，而且已經(jīng)引起了全球各個(gè)國(guó)家的重視。從政府到企業(yè)，從中央到地方，都開始物流戰(zhàn)略的規(guī)劃與實(shí)施，并且開始物流信息系統(tǒng)的建設(shè)。該文以物流路徑規(guī)劃系統(tǒng)為研究對(duì)象，介紹了一些著名的最優(yōu)路徑規(guī)劃算法。在深入分析節(jié)約算法的基礎(chǔ)上，提出并實(shí)現(xiàn)了配合Dijkstra算法的節(jié)約里程表算法，開發(fā)了以本文算法為核心的實(shí)時(shí)物流路徑規(guī)劃與模擬系統(tǒng)。

關(guān)鍵詞：物流信息系統(tǒng)；車輛路徑問(wèn)題；路徑規(guī)劃；節(jié)約里程算法；B2C

中圖分類號(hào)：TP181 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：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

近些年來(lái)，顧客需求不斷多樣化、企業(yè)競(jìng)爭(zhēng)更加激烈、全球制造的概念不斷發(fā)展，不僅我國(guó)政府也將物流視為新的經(jīng)濟(jì)熱點(diǎn)，而且已經(jīng)引起了全球各個(gè)國(guó)家的重視。

早在20世紀(jì)60～70年代，發(fā)達(dá)國(guó)家日本、歐美就開始從事和研究物流，不斷發(fā)展LIS系統(tǒng)，我國(guó)的LIS系統(tǒng)還處于企業(yè)各自開發(fā)，僅供企業(yè)內(nèi)部使用的階段[1]。

本文以物流路徑規(guī)劃系統(tǒng)為研究對(duì)象，分析現(xiàn)有的各類最優(yōu)路徑規(guī)劃算法，對(duì)比了各種路徑規(guī)劃算法的優(yōu)缺點(diǎn)。在深入分析節(jié)約算法的基礎(chǔ)上，提出并實(shí)現(xiàn)了配合Dijkstra的節(jié)約里程表算法的實(shí)時(shí)路徑模擬規(guī)劃系統(tǒng)。

一般的單車輛路徑規(guī)劃（VRP）是如下定義的：給出一張強(qiáng)連通的復(fù)雜圖，該圖由一組的頂點(diǎn)[V]，一組無(wú)向邊[E]和一組有向弧[A]組成，并且有子集[V'?V，E'?E，A'?A]并且在邊和弧上有非負(fù)權(quán)值，找到一個(gè)包含[V']，[E']，[A']且總權(quán)值最小的路線[2]。

在100個(gè)結(jié)點(diǎn)的前提下，路徑規(guī)劃耗費(fèi)的計(jì)算時(shí)間均不超過(guò)1.8秒，可見(jiàn)本系統(tǒng)實(shí)現(xiàn)算法的高效性和合理性。

4 總結(jié)

本文以物流路徑規(guī)劃系統(tǒng)為研究對(duì)象，介紹了一些著名的最優(yōu)路徑規(guī)劃算法，對(duì)比了各種路徑規(guī)劃算法的優(yōu)缺點(diǎn)。在深入分析節(jié)約算法的基礎(chǔ)上，提出了配合迪杰斯特拉算法的節(jié)約里程表算法，然后以此為核心，對(duì)實(shí)時(shí)路徑規(guī)劃模擬系統(tǒng)進(jìn)行了需求分析，概要設(shè)計(jì)，詳細(xì)設(shè)計(jì)，最終編碼實(shí)現(xiàn)了實(shí)時(shí)路徑規(guī)劃模擬系統(tǒng)。

參考文獻(xiàn)：

[1] 劉永清，肖忠東，董安邦.基于三層C/S，B/S集成的物流信息系統(tǒng)體系結(jié)構(gòu)的研究[J].湖南科技大學(xué)學(xué)報(bào)：自然科學(xué)版，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] 何蓮蓮，石峰，周懷北.改進(jìn)的蟻群算法在2D HP模型中的應(yīng)用[J].武漢大學(xué)學(xué)報(bào)： 理學(xué)版， 2005， 51（1）：33-8.

[4] 宋偉剛，張宏霞，佟玲.有時(shí)間窗約束非滿載車輛調(diào)度問(wèn)題的節(jié)約算法[J].東北大學(xué)學(xué)報(bào)：自然科學(xué)版，2006，27（1）： 65-8.