一種基于Voronoi圖求解車輛路徑問題的混合啟發(fā)式算法

摘 要:針對(duì)由多個(gè)配送中心和多個(gè)客戶點(diǎn)組成的物流網(wǎng)絡(luò)中的車輛路徑問題，提出了一種基于“集群第一，路線第二”的路徑優(yōu)化策略，即首先使用Voronoi分割對(duì)配送區(qū)域進(jìn)行劃分，然后引入綜合插入算法和變鄰域搜索算法的混合啟發(fā)式算法求解配送區(qū)域內(nèi)車輛路徑問題。通過算例和應(yīng)用系統(tǒng)的分析與驗(yàn)證表明，該混合算法既能獲取質(zhì)量較優(yōu)解，同時(shí)也具有較好的實(shí)時(shí)性，能較好地滿足實(shí)際應(yīng)用需求。

關(guān)鍵詞:Voronoi分割; 混合啟發(fā)式算法; 插入式算法; 變鄰域搜索; 鄰接信息

中圖分類號(hào):TP301.6

文獻(xiàn)標(biāo)志碼:A

文章編號(hào):1001-3695(2010)02-0515-04

doi:10.3969/j.issn.1001-3695.2010.02.031

Hybrid heuristic algorithm using Voronoi diagram forvehicle routing problem

ZHANG Zhi-jun1， LI-Feng1 ， CAO Bu-yang2

(1.School of Computer Science Telecommunication Engineering， Jiangsu University， Zhenjiang Jiangsu 212013，China; 2.School of Software Engineering， Tongji University， Shanghai 201804， China)

Abstract:This paper proposed the optimization strategy of vehicle route based on the strategy of “cluster first， route second” which aimed at the vehicle route problems made up of multiple dispatching centers and sale-points in the logistics network. Firstly， used Voronoi tessellation to divide the dispatching regions， and then introduced a hybrid heuristic algorithm which combined the plug-in algorithm and the variable neighbor search(VNS) algorithm in order to solve the optimization problems of vehicle route in dispatching regions. This hybrid algorithm can achieve a better solution to vehicle route optimization problems through the experiment results and the analysis and verification of the application system. At the same time， it also has good real-time which can better meet the needs of practical application.

Key words:Voronoi tessellation; hybrid heuristic algorithm; CI; VNS; adjacency information

0 引言

車輛路徑問題(vehicle routing problem，VRP)一直是運(yùn)籌學(xué)、管理學(xué)、計(jì)算機(jī)科學(xué)等領(lǐng)域的研究熱點(diǎn)問題，在現(xiàn)實(shí)生活中有著廣泛的應(yīng)用，是一個(gè)具有重要理論意義和實(shí)際應(yīng)用價(jià)值的研究課題。車輛路徑問題一般定義為:對(duì)一系列客戶，組織適當(dāng)?shù)男熊嚶肪€，使車輛有序地通過，在滿足一定的約束條件(如貨物需求量、發(fā)貨量、交貨時(shí)間、車輛容量限制、行駛里程限制、時(shí)間限制等)下，在客戶可以接受的演算時(shí)間內(nèi)，給出盡可能優(yōu)化的路線規(guī)劃方案，最大限度地降低客戶的運(yùn)營(yíng)成本(運(yùn)營(yíng)時(shí)間、距離或其他費(fèi)用)。該問題1959年由Dantzig等人[1]提出后，幾十年來已取得大量研究成果。由于VRP是NP-hard問題，難以用精確算法求解，對(duì)此類問題求解方法的研究主要集中于能在較短時(shí)間內(nèi)給出較優(yōu)解的啟發(fā)式算法。

1960年，Clarke等人[2]首先提出一種啟發(fā)式節(jié)省法來建立車隊(duì)配送路線。啟發(fā)式節(jié)省法簡(jiǎn)單易懂、求解速度快，但只適合求解小型、簡(jiǎn)單的VRP。1960—1970年，提出簡(jiǎn)單啟發(fā)式算法，包括各種局部改善啟發(fā)式算法和貪婪法(greedy)等。1970—1980年，提出一些以數(shù)學(xué)規(guī)劃為主的啟發(fā)式算法，包括指派法、集合分割法和集合涵蓋法。從1990年開始至今，研究主要集中在一些較新的算法，包括利用嚴(yán)謹(jǐn)啟發(fā)式算法、人工智能算法等。在文獻(xiàn)[3，4]中，介紹了這些算法的詳細(xì)信息。

按照國(guó)家煙草專賣局要求，要建立體系完善、行業(yè)統(tǒng)一、分級(jí)管理、工商協(xié)同、信息共享、成本合理、快速控制、高度信息化和適度自動(dòng)化的行業(yè)現(xiàn)代物流系統(tǒng)。結(jié)合煙草行業(yè)客戶點(diǎn)數(shù)量多、分布密度大、規(guī)模大等特點(diǎn)，本文針對(duì)由多個(gè)配送中心和多個(gè)客戶點(diǎn)組成的物流網(wǎng)絡(luò)中的車輛路徑問題，提出了一種基于“集群第一，路線第二”的路徑優(yōu)化策略。配送區(qū)域作為集群處理，能夠減少問題的復(fù)雜度，提供更明確的實(shí)施方向和更強(qiáng)的可操作性;在配送區(qū)域內(nèi)對(duì)車輛路線進(jìn)行規(guī)劃，能提供更加詳細(xì)的路線配送方案。

1 帶時(shí)間窗車輛路徑問題描述

本文結(jié)合煙草行業(yè)客戶數(shù)眾多、規(guī)模大等特點(diǎn)，特將煙草行業(yè)帶時(shí)間窗的車輛路徑問題(VRPTW)描述為:首先使用Voronoi分割將配送圈劃分為多個(gè)配送區(qū)域，在每個(gè)配送區(qū)域內(nèi)，有一配送中心D。該配送中心D擁有k輛車，容量為QK，k=1，2，…，K;有L個(gè)客戶點(diǎn)要配送;第i個(gè)客戶點(diǎn)的需求量是Ci，滿足max Ci

VRPTW可以分為硬時(shí)間窗VRP和軟時(shí)間窗VRP兩類。硬時(shí)間窗VRP是指每項(xiàng)配送必須在要求的時(shí)間范圍內(nèi)完成;軟時(shí)間窗VRP是指如果某項(xiàng)配送不能在要求的時(shí)間內(nèi)完成，則給予一定的懲罰:若車輛在αi之前到達(dá)客戶i，車輛在此等待，增加時(shí)間成本;若車輛在βi之后到達(dá)客戶i，服務(wù)被延遲，須支付一定的罰金成本。

本文引用文獻(xiàn)[5]提出的軟時(shí)間窗VRP的數(shù)學(xué)模型:V={1，2，…，L}為客戶集，V0={0}∪V，0表示配送中心。令i∈V0，即配送中心和客戶點(diǎn)均以i編號(hào)，定義變量如下:

xijk=1 如果有第k輛車由客戶i到客戶j0 其他

令dij表示從客戶i到客戶j的距離成本，si表示車輛到達(dá)客戶i的時(shí)刻，vi表示車輛在客戶點(diǎn)i的等待服務(wù)時(shí)間，有vi=max{αi-si，0}; wi表示車輛在客戶點(diǎn)i的服務(wù)延遲時(shí)間，有wi=max{si-βi，0};1為在αi之前到達(dá)客戶點(diǎn)i等待的單位時(shí)間成本;2為在βi之后到達(dá)客戶點(diǎn)i延遲的單位罰金成本。因此，若車輛在αi之前到達(dá)客戶i，則會(huì)增加等待成本1(αi-si);若車輛在βi之后到達(dá)客戶i，則將增加罰金成本2(si-βi)。得到式(1)所示軟時(shí)間窗VRP目標(biāo)成本函數(shù):

min z=∑i∑j∑kdijxijk+1∑Li=1max{ai-si，0}+2∑Li=1max{si-βi，0}(1)

式(1)中，當(dāng)1=2→∞時(shí)，該目標(biāo)函數(shù)可以表示硬時(shí)間窗VRP。若車輛到達(dá)客戶i的時(shí)刻si<αi，即車輛處于等待服務(wù)時(shí)間，有αi-si>0，si-βi<0，所以vi=αi-si，wi=0;同樣若si>βi，即車輛處于服務(wù)延遲時(shí)間vi=0，wi=si-βi。

在任務(wù)分配(將客戶點(diǎn)插入到路線r)過程中，客戶k的插入方式如圖1所示，在路線r中將客戶點(diǎn)k插入到客戶i和j之間。由于客戶k的插入，客戶i到j(luò)的路線將被刪除，致使路線r的行駛距離、客戶的服務(wù)時(shí)間等都要相應(yīng)地發(fā)生變化。

本文引入一評(píng)價(jià)因子的公式表示客戶k插入路線r后行駛距離變化量Δdr、等待服務(wù)時(shí)間變化量Δvr和服務(wù)延遲時(shí)間變化量Δwr的權(quán)重和，如式(2)所示。其中1、2分別是等待的單位時(shí)間成本和延遲的單位罰金成本。

OE=∑kr=1Δdr+1∑kr=1Δvr+2∑kr=1Δwr(2)

由于客戶點(diǎn)k有很多插入位置，選取評(píng)價(jià)因子最小的位置作為客戶點(diǎn)的最終插入位置。

2 基于Voronoi分割配送區(qū)域的劃分

2.1 Voronoi的概述

Voronoi圖定義[6，7]如下:假設(shè)P={P1，P2，…，Pn}(3<n<∞)是歐幾里德平面上一個(gè)離散點(diǎn)集，任意三個(gè)點(diǎn)不共線，任意四個(gè)點(diǎn)不共圓，用d(pi，pj)表示點(diǎn)(pi，pj)的歐幾里德距離。設(shè)x∈P，則區(qū)域V={x∈E2|d(x，pi)≤d(x，pj)，i，j=1，2…，n，i≠j}稱為Voronoi多邊形，各點(diǎn)的多邊形共同組成Voronoi圖。

相關(guān)性質(zhì)如下:

a)影響范圍特性。每一個(gè)種子點(diǎn)惟一對(duì)應(yīng)一個(gè)Voronoi多邊形，凡是落在Voronoi多邊形內(nèi)的任一客戶點(diǎn)與該種子點(diǎn)的距離最小。種子點(diǎn)可以看成是該區(qū)域的配送中心。

b)鄰接信息的相似特性。Voronoi多邊形中客戶點(diǎn)的近似信息是該點(diǎn)所對(duì)應(yīng)Voronoi多邊形鄰域點(diǎn)的集合。利用鄰域近似信息來實(shí)現(xiàn)降維，可將無向圖G=(V，A)降為G′=(V，A′)。G′是G的一個(gè)子圖，A′是A鄰域信息的集合，這是一個(gè)降低圖復(fù)雜度的方法。

根據(jù)煙草行業(yè)的特點(diǎn)，客戶數(shù)眾多，將煙草行業(yè)的物流配送設(shè)計(jì)為多配送中心和多客戶點(diǎn)的兩級(jí)物流配送模式。依據(jù)Voronoi多邊形性質(zhì)先對(duì)配送區(qū)域進(jìn)行劃分，確定客戶離哪個(gè)配送中心的距離最近，進(jìn)而優(yōu)化各個(gè)配送中心的配送對(duì)象，然后在配送區(qū)域內(nèi)求解車輛路徑問題。

2.2 自實(shí)現(xiàn)Voronoi多邊形的生成和配送區(qū)域的劃分

按照定義[8]形成Voronoi多邊形要計(jì)算點(diǎn)間連線及其垂直平分線的交點(diǎn)，并且要保證這些垂直平分線圍成的多邊形內(nèi)只包括一個(gè)種子點(diǎn)，保存和判斷的因素過多，因此這種方法實(shí)現(xiàn)起來比較困難，而使用Delauney三角形建模則要容易一些。同時(shí)在GIS中，Voronoi多邊形是由ArcInfo生成的，并且ArcInfo價(jià)格昂貴。因此在本文研究中，基于開源代碼和Delau-ney三角網(wǎng)來生成Voronoi多邊形，方法如下:

a)種子點(diǎn)自動(dòng)構(gòu)建三角網(wǎng)，即構(gòu)建Delaunay三角網(wǎng)，對(duì)種子點(diǎn)和形成的三角形編號(hào)，記錄每個(gè)三角形是由哪三個(gè)種子點(diǎn)構(gòu)成的。

b)找出與每個(gè)種子點(diǎn)相鄰的所有三角形的編號(hào)并記錄下來。在已構(gòu)建的Delaunay三角網(wǎng)中找出具有一個(gè)相同種子點(diǎn)的所有三角形。

c)對(duì)與每個(gè)種子點(diǎn)相鄰的三角形按順時(shí)針或逆時(shí)針方向排序，以便下一步連接生成Voronoi多邊形。

d)計(jì)算每個(gè)三角形的外接圓圓心，根據(jù)每個(gè)種子點(diǎn)的相鄰三角形，連接這些相鄰三角形的外接圓圓心，得到Voronoi多邊形。圖2為客戶點(diǎn)空間分布，圖3為用自實(shí)現(xiàn)Voronoi多邊形獲得的配送區(qū)域的一個(gè)劃分。

通過建立上述Voronoi多邊形(圖3)，整個(gè)配送圈就被分成若干個(gè)不同的配送區(qū)域，每個(gè)配送區(qū)域就惟一對(duì)應(yīng)一個(gè)配送中心和若干個(gè)客戶點(diǎn)。由Voronoi多邊形的性質(zhì)a)可知，對(duì)任意的一個(gè)客戶點(diǎn)，很容易獲得哪個(gè)配送中心離該客戶點(diǎn)的距離最近，從而實(shí)現(xiàn)對(duì)配送區(qū)域的劃分。

3 配送區(qū)域內(nèi)車輛路徑問題

本文提出的混合啟發(fā)式算法CI_VNS包括三個(gè)階段:建立距離矩陣、構(gòu)造初始解、路線改進(jìn)與優(yōu)化。

3.1 建立距離矩陣

距離矩陣表示為d11d12…d1nd21d22…d2ndn1dn2…dnn。

矩陣中，元素dij(i≠j，1≤i，j≤n)是GIS街道網(wǎng)絡(luò)數(shù)據(jù)距離，表示任意兩個(gè)點(diǎn)(配送中心或客戶點(diǎn))之間的行駛距離。任意兩點(diǎn)理論的行駛時(shí)間tij(i≠j，1≤i，j≤n)，且tij=dij/v(v表示理論上車輛在某一路段行駛的速度)。此矩陣為構(gòu)造初始解、路線改進(jìn)與優(yōu)化提供最基本的信息。

3.2 任務(wù)分配—構(gòu)造初始解

由距離矩陣可知，配送中心到任意客戶點(diǎn)的距離、時(shí)間和任意兩個(gè)客戶點(diǎn)之間的距離、時(shí)間都已經(jīng)確定，然后就是解決車輛路徑問題，即車輛路線最優(yōu)化問題。構(gòu)造車輛路徑問題的算法即是把客戶點(diǎn)分配給相應(yīng)的車輛。把客戶點(diǎn)分配給車輛時(shí)，通過加權(quán)的方法把時(shí)間窗因素合并成一個(gè)評(píng)價(jià)因子OE(式(2))，選取插入評(píng)價(jià)因子最小的客戶點(diǎn)分配給相應(yīng)的車輛。本文將采用插入法構(gòu)造初始路線，也稱為初始可行解的構(gòu)建，其步驟如下:

a)從尚未訪問的客戶點(diǎn)中確定出發(fā)點(diǎn)(配送中心)和終點(diǎn)，為每輛車r分配最初的一條行駛路線，此行駛路線只包括配送中心點(diǎn)和終點(diǎn)。

b)計(jì)算每一輛車r相應(yīng)的行駛距離變化量Δdr，等待服務(wù)時(shí)間數(shù)量Δvr和服務(wù)延遲時(shí)間數(shù)量Δwr。

c)在路線r中兩個(gè)連續(xù)的客戶點(diǎn)間插入一個(gè)未被分配的客戶點(diǎn)i，定義U為全部未被訪問客戶點(diǎn)的集合。對(duì)每一條路線r和其中可插入的位置k，未分配客戶點(diǎn)i的插入評(píng)價(jià)因子定義為:

OE=∑kr=1Δdr+1∑kr=1Δvr+2∑kr=1Δwr

其中:1、2分別是等待的單位時(shí)間成本和延遲的單位罰金成本。如果客戶點(diǎn)i在位置k的插入引起路線r的容量超過Qr，那么其插入評(píng)價(jià)因子被定義為極大。

d)若客戶點(diǎn)j(i≠j，j∈V)插入的評(píng)價(jià)因子OE取最小值，則選擇客戶點(diǎn)j并將其插入至r路線上。客戶點(diǎn)j插入路線r后，其行駛距離和時(shí)間、等待服務(wù)時(shí)間、服務(wù)延遲時(shí)間都會(huì)相應(yīng)地被修改。

e)當(dāng)客戶點(diǎn)j插入路線后，令U=U\\{j}。若U≠，算法通過考慮所有可能的路線和位置為在U中所有客戶更新插入評(píng)價(jià)因子并重復(fù)上述客戶分配步驟;若U=，算法即可繼續(xù)進(jìn)行線路改進(jìn)程序，亦可停止。其軟時(shí)間窗VRP運(yùn)輸總成本函數(shù)為

min z=∑i∑j∑kdijxijk+1∑Li=1max{aj-sj，0}+2∑Li=1max{sj-βj，0}

3.3 路線改進(jìn)與優(yōu)化——變鄰域信息搜索

變鄰域搜索的基本步驟為:從構(gòu)造的初始解出發(fā)，選擇一種鄰域結(jié)構(gòu)進(jìn)行局部搜索，直至找到局部最優(yōu)解;以當(dāng)前局部最優(yōu)解作為初始解，使用另一種鄰域結(jié)構(gòu)繼續(xù)進(jìn)行局部搜索。

在引入變鄰域信息搜索之前需要先定義一組鄰域結(jié)構(gòu)。算法CI_VNS中使用兩種求解VRP問題常用的鄰域結(jié)構(gòu):插入和交換。引用文獻(xiàn)[9]的思想、文獻(xiàn)[10]作為實(shí)驗(yàn)結(jié)果:先插入、后交換順序，算法性能表現(xiàn)較好。

1)插入

將解S中的某個(gè)客戶點(diǎn)i從當(dāng)時(shí)位置p1移到S的另外一個(gè)位置p2(p1和p2可以屬于同一條路徑，也可以屬于不同路徑)，當(dāng)某條路徑上沒有客戶點(diǎn)時(shí)，刪除該路徑，從而使車輛個(gè)數(shù)最少，便產(chǎn)生新解S1。路線間的改進(jìn)引入Voronoi多邊形鄰接相似信息的降維方法(插入方法)以減少問題的復(fù)雜度。如圖4所示，有路線R1={0，12，8，2，9，4，7，0}和R2={0，5，6，1，3，10，11，0}，節(jié)點(diǎn)0表示配送中心。路線R2中P1的鄰域相似信息為P1={8，2，4}，則將路線R2中的客戶點(diǎn)1插入至路線R1的客戶點(diǎn){8，2，4}的前面(僅有三種插入方案)。客戶點(diǎn)1有七個(gè)插入方案(箭頭所示)，利用Voronoi多邊形鄰域相似信息，客戶點(diǎn)1就只插入到客戶點(diǎn){8，2，4}之一的前面(虛線箭頭)，從而達(dá)到降低其復(fù)雜度的效果。

2)交換

將解S1中的客戶i和j的位置互換(i和j可以屬于同一條路徑，也可以屬于不同路徑)，產(chǎn)生新解S2。同樣，路線間的改進(jìn)引入Voronoi多邊形鄰域相似信息的降維方法(交換方法)。如圖5所示，有路線R1={0，12，8，2，9，4，7，0}和R2={0，5，6，1，3，10，11，0}，路線R2中P1的鄰域相似信息P1={8，2，4}，路線R1中P8的鄰域相似信息P8={5，1，3}。因?yàn)镻1的鄰域相似信息有客戶點(diǎn){8}及P8的鄰域相似信息中有客戶點(diǎn){1}，根據(jù)Voronoi多邊形鄰域相似信息的性質(zhì)b)可將R1、R2兩路線上的客戶點(diǎn){1}和{8}互換(虛線箭頭)，從而達(dá)到降低其復(fù)雜度的效果。

3.4 算法流程(圖6)

在現(xiàn)實(shí)的路線規(guī)劃中，需要考慮兩種情況，并且基于實(shí)際情況對(duì)該算法進(jìn)行改進(jìn):

a)需要整體處理的(主要針對(duì)農(nóng)村沒有道路及菜市場(chǎng)等不能分割的零售戶)進(jìn)行打包處理，設(shè)置停靠點(diǎn)，需要打包的客戶點(diǎn)和停靠點(diǎn)建立綁定。

b)客戶點(diǎn)標(biāo)注在電子地圖上，所有的客戶通過計(jì)算與所在的道路進(jìn)行綁定，對(duì)于距離之外的客戶點(diǎn)指定對(duì)應(yīng)的道路。

4 實(shí)驗(yàn)結(jié)果分析

4.1 算法測(cè)試

算法性能測(cè)試環(huán)境為:Visual Studio 2008、Arcgis9.3、Intel Core(TM)2 Duo CPU E8400 3.00 GHz處理器和4 GB DDR2內(nèi)存。通過大量的實(shí)驗(yàn)將參數(shù)設(shè)置如下:1=5(等待服務(wù)單位時(shí)間成本)，2=10(延遲服務(wù)單位時(shí)間成本)。

為測(cè)試算法CI_VNS的性能，采用一個(gè)煙草配送實(shí)例進(jìn)行測(cè)試。在城市煙草配送中，將整個(gè)城市看做是一個(gè)配送圈，使用Voronoi分割將配送圈分成農(nóng)網(wǎng)、城網(wǎng)、偏遠(yuǎn)、環(huán)城路四個(gè)配送區(qū)域，將問題劃分為小規(guī)模(客戶點(diǎn)為50~200)問題，并分別進(jìn)行三組實(shí)驗(yàn)。

第一組實(shí)驗(yàn)只使用插入算法CI，第二組實(shí)驗(yàn)只使用變鄰域搜索算法VNS，第三組實(shí)驗(yàn)是本文提出的混合算法CI_VNS，在三組實(shí)驗(yàn)中其他條件設(shè)置均相同。本文選取五次路線優(yōu)化實(shí)驗(yàn)數(shù)據(jù)的平均值，結(jié)果如表1、2所示。在表1中，第一列為問題規(guī)模，其他幾列是每組算法中所得出的最優(yōu)解的運(yùn)輸總成本，最后一列是本文算法得出的最優(yōu)解運(yùn)輸總成本。表2為各組算法求解所需要的時(shí)間。

表1 混合啟發(fā)式算法的測(cè)試結(jié)果

problemCIVNSCI_VNS

valuevaluevalue

50525.36524.68498.67

75844.39864.56835.50

100853.93874.76845.69

1201 042.711 042.221 028.42

1501 347.361 324.611 311.34

1991 427.401 428.401 374.83

表2 混合啟發(fā)式算法的測(cè)試結(jié)果

problemCIVNSCI_VNS

t/st/st/s

501.744.755.84

756.156.368.69

1009.8513.9426.84

12022.3735.6648.64

15038.1546.5669.95

19949.7659.85122.71

通過表1可以看出，混合啟發(fā)式算法CI_VNS求解車輛路徑問題的質(zhì)量(value)明顯優(yōu)于單獨(dú)使用算法CI和VNS，實(shí)驗(yàn)表明將CI和VNS結(jié)合是有效的。在表2中，雖然該混合算法所消耗的時(shí)間明顯比前兩種算法單獨(dú)使用時(shí)所需要的時(shí)間要長(zhǎng)，但仍能在可接受的時(shí)間內(nèi)得到問題的較優(yōu)解。

為進(jìn)一步驗(yàn)證本文算法CI_VNS的性能，表3是算法CI_VNS與現(xiàn)有算法在min算例上求得的最優(yōu)解的路徑長(zhǎng)度的比較。結(jié)果表明，混合算法CI_VNS求解的最優(yōu)解路徑長(zhǎng)度優(yōu)于文獻(xiàn)[12~14]中算法所求解的最優(yōu)解路徑長(zhǎng)度。

表3 算法CI_VNS與現(xiàn)有算法在min算例上的比較

problemMin[12]Dethloff[13]MontaneGalavo[14]CI_VNS

MIN2294919190

4.2 算法的應(yīng)用

目前該策略已經(jīng)成功運(yùn)用于煙草物流行業(yè)。根據(jù)所收集的空間數(shù)據(jù)和屬性數(shù)據(jù)，建立該煙草行業(yè)地理信息數(shù)據(jù)庫(kù)。以空間距離最短為原則，首先使用Voronoi分割對(duì)配送區(qū)域進(jìn)行劃分，然后在配送區(qū)域內(nèi)求解車輛路徑問題。在圖7中，煙草物流網(wǎng)絡(luò)配送原型系統(tǒng)包括三個(gè)模塊:配送區(qū)域模塊、車輛路徑模塊和軟時(shí)間窗顯示模塊。使用Voronoi分割可以將整個(gè)配送圈劃分為四個(gè)配送區(qū)域:農(nóng)網(wǎng)、城網(wǎng)、偏遠(yuǎn)、環(huán)城路;地圖中顯示的是偏遠(yuǎn)區(qū)域中配送路線，不同的車輛對(duì)應(yīng)不同顏色的路線;軟時(shí)間窗顯示的是車輛配送客戶所對(duì)應(yīng)的服務(wù)時(shí)間、等待時(shí)間等。

5 結(jié)束語(yǔ)

本文基于“集群第一，路線第二”策略，把煙草行業(yè)的物流配送問題分解為兩個(gè)步驟:利用Voronoi多邊形的相關(guān)特性，首先使用Voronoi分割對(duì)煙草配送區(qū)域進(jìn)行劃分，然后引入綜合插入式算法和變鄰域搜索算法的混合啟發(fā)式算法求解配送區(qū)域內(nèi)車輛路徑，該算法還引入Voronoi多邊形鄰接相似信息的降維方法。

本文結(jié)合現(xiàn)實(shí)情況，將客戶點(diǎn)進(jìn)行打包處理，以降低問題的復(fù)雜度，提高求解的質(zhì)量，加速算法的收斂。最后本文通過實(shí)驗(yàn)驗(yàn)證該混合啟發(fā)式算法的求解性能優(yōu)于單一算法的求解性能。目前該算法已經(jīng)成功運(yùn)用于煙草物流原型系統(tǒng)中，并取得很好的效果。事實(shí)證明，該混合啟發(fā)式算法是一種在實(shí)踐中可用的算法，同時(shí)具有較好的實(shí)時(shí)性，能較好地滿足實(shí)際應(yīng)用需求。

參考文獻(xiàn):

[1]DANTZIG G B， RAMSER J H. The truck dispatching problem[J].Management Science，1959，6(1):80-91.

[2]CLARKE G，WRIGHT J. Scheduling of vehicles from central depot to a number of delivery points[J]. Operations Research，1964，12(4):568-581.

[3]LAPROTE G. The vehicle routing problem:an overview of exact and approximation algorithms[J]. European Journal of Operational Research，1992，5(9):345-358.