開放式車輛路徑的單親遺傳禁忌搜索優(yōu)化研究

陳丕影，楊斌

（1.上海海事大學(xué)信息工程學(xué)院，上海　201306；2.上海海事大學(xué)物流研究中心，上海 201306）

開放式車輛路徑的單親遺傳禁忌搜索優(yōu)化研究

陳丕影1，楊斌2

（1.上海海事大學(xué)信息工程學(xué)院，上海201306；2.上海海事大學(xué)物流研究中心，上海 201306）

0　引言

開放式車輛路徑問題（Open VRP，OVRP）指車輛在服務(wù)完其所有客戶之后，結(jié)束于最后所服務(wù)的客戶點(diǎn)，而不必返回原出發(fā)地點(diǎn)的問題。OVRP在各種物流配送的路線優(yōu)化中普遍存在。例如，第三方物流的掛靠車輛。因?yàn)檐囕v無需返回始發(fā)地，因此其行駛路線是開放的。

Brandao［1］使用禁忌搜索求解OVRP問題，鐘石泉等［2］使用遺傳算法求解帶容量、時(shí)間窗的OVRP。李延暉［3］使用蟻群優(yōu)化算法求解沿途不活的MOVRP。S.A. MirHassani，N.Abolghasemi使用粒子群優(yōu)化算法求解OVRP。於世為［6］等使用遺傳算法與禁忌搜索相混合的算法求解OVRP。李惠等使用單親遺傳禁忌搜索算法解決了手術(shù)的排程問題。

本文針對OVRP，提出了一種基于PGA和TS的混合優(yōu)化算法。該混合算法首先使用PGA進(jìn)行全局搜索，經(jīng)過PGA優(yōu)化后的種群，其所有個(gè)體再以一定的概率進(jìn)行TS局部搜索，提高了運(yùn)算速度。而TS的局部搜索使用交換算子生成鄰域，而且只對同一輛車所服務(wù)的客戶點(diǎn)進(jìn)行優(yōu)化。

1　問題描述與數(shù)學(xué)模型

根據(jù)配送中心與客戶位置、實(shí)際的交通運(yùn)輸情況以及物流配送情況抽象出一個(gè)無向圖，用G=（V，K，D）表示配送圖，其中V、K表示節(jié)點(diǎn)屬性，D表示邊屬性。V= ｛vi，0≤i≤n｝表示配送中心和客戶，配送中心為v0，需要服務(wù)的客戶數(shù)為n；K=｛k，1≤k≤m｝表示物流公司擁有的車輛數(shù)且車的型號以及載重量相同；D=｛dij，0≤i≤n，0≤j≤n｝表示配送中心與客戶以及客戶與客戶之間的距離；qi（1≤i≤n）表示客戶i訂單需求量；Q表示每輛車的額定載重量；CFk表示車輛k的固定成本，CRk表示車輛k正常8小時(shí)上班單位時(shí)間勞動(dòng)成本，COk表示車輛k加班單位時(shí)間勞動(dòng)成本；Tsk表示車輛k的出發(fā)時(shí)間，Tok表示車輛k完成配送任務(wù)的時(shí)間，TRk表示車輛k正常上班時(shí)間且TRk=min（Tok-Tsk，8）；TOk表示車輛k加班時(shí)間且TOk=max（Tok-Tsk-8，0）；tij表示從i到j(luò)的車輛行駛時(shí)間且tij=；Tjk表示車輛k到達(dá)j的時(shí)間；si表示客戶點(diǎn)i的服務(wù)時(shí)間，則 Tjk=Tik+si+tij×xijk，若

j=0，則Tjk=0。［ei，li］表示客戶i的服務(wù)時(shí)間窗，p為車輛提前到達(dá)客戶點(diǎn)的單位時(shí)間等待成本；q為車輛延遲到達(dá)客戶點(diǎn)的單位時(shí)間懲罰成本。

車輛路徑模型：

目標(biāo)函數(shù)（1）表示成本最小化的車輛路徑模型，主要由六部分組成，車輛行駛成本、車輛固定成本、正常上班勞動(dòng)成本、加班勞動(dòng)成本、早到等待成本、延遲到達(dá)懲罰成本。式（2）表示車輛載重約束。式（3）和式（4）表示每個(gè)客戶只能有一輛車為其服務(wù)，且服務(wù)次數(shù)僅為一次。式（5）避免客戶之間子回路。式（6）表示車輛只能由配送中心出發(fā)。式（7）表示配送車輛無需返回始發(fā)地。式（8）是典型的流守恒方程，確保每輛車路線的連續(xù)性，即車輛出入平衡。式（9）和式（10）表示0-1整數(shù)變量約束。

2　單親遺傳禁忌搜索算法

單親遺傳算法 （Partheno-Genetic Algorithm，PGA）只作用在一條染色體，與傳統(tǒng)遺傳算法原理相同，通過選擇和變異繁殖后代，簡化了操作流程，提高了運(yùn)算效率。禁忌搜索算法（Tabu Search，TS）的核心是搜索過程具有記憶功能，因此具有較強(qiáng)的局部搜索能力。針對本文的問題，設(shè)計(jì)一種將PGA和TS相結(jié)合的單親遺傳禁忌搜索算法（PGATS），即避免了單親遺傳算法早熟現(xiàn)象的發(fā)生，又簡化了操作步驟。

編碼是應(yīng)用遺傳算法要解決的首要問題。本文采用自然數(shù)編碼方式，所形成的染色體是由車輛編號和客戶編號排列組成的有序字符串，每條染色體代表求解問題的一個(gè)解，即代表一條路徑。例如，配送中心0需要完成一次配送任務(wù)，該項(xiàng)任務(wù)需將貨物送至8個(gè)客戶點(diǎn)。用1～8的自然數(shù)代表8個(gè)客戶點(diǎn)。首先在1～8內(nèi)隨機(jī)生成一個(gè)序列，如｛1，4，3，6，8，5，2，7｝，然后根據(jù)客戶點(diǎn)的需求量和車輛的裝載能力進(jìn)行解碼，按順序從左向右依次加入一個(gè)點(diǎn)，然后判斷是否超出車輛的裝載能力，按照加入的客戶點(diǎn)排成一個(gè)序列，即為一條子路徑。然后從未被訪問的點(diǎn)重復(fù)此過程，獲得下一條子路徑，直到訪問完所有客戶點(diǎn)為止。最后用0解碼先前形成的序列，即｛0，1，4，3，6，0，8，5，2，0，7｝得到3條子路徑，每條子路徑被稱為一個(gè)基因，此處的染色體有3個(gè)基因組成，即01436，0852，07，因此得到的3條子路徑為：

子路徑1：配送中心0—客戶點(diǎn)1—客戶點(diǎn)4—客戶點(diǎn)3—客戶點(diǎn)6

子路徑2：配送中心0—客戶點(diǎn)8—客戶點(diǎn)5—客戶點(diǎn)2

子路徑3：配送中心0—客戶點(diǎn)7

PGA只通過選擇和變異操作繁殖后代。文獻(xiàn)［5］證明PGA只有在精英保留操作時(shí)才能達(dá)到全局收斂。因此本文采用精英保留和輪盤賭相結(jié)合的方法對種群中個(gè)體進(jìn)行優(yōu)生劣汰操作，既保證了最優(yōu)個(gè)體直接遺傳到下一代，又達(dá)到了算法全局收斂的效果。

移位算子采用單點(diǎn)移位，即按一定概率ps將一條染色體中的一個(gè)基因作移位操作，但必須滿足一個(gè)限制條件，即移位操作不能導(dǎo)致新父節(jié)點(diǎn)的容量溢出。操作過程如圖1所示：

圖1　移位操作

倒位算子采用單點(diǎn)倒位，即按一定概率pi將一條染色體中的一個(gè)子串作倒位操作。此處無需判斷父節(jié)點(diǎn)的容量溢出情況。操作過程如圖2所示：

圖2　倒位操作

變異算子采用單點(diǎn)變異，即按一定概率pv將一條染色體上的某個(gè)基因位上的基因取其同序基因集中的其它值的操作過程。由于編碼方式是自然數(shù)編碼，不允許出現(xiàn)重復(fù)的編號，采取方法是改變一個(gè)基因位的同時(shí)改變另一相同序號的基因位。操作過程如圖3所示：

圖3　變異操作

禁忌搜索算法將人工智能與局部鄰域搜索算法相結(jié)合，搜索途中可接受劣解，因此有較強(qiáng)的“爬山”能力。TS鄰域操作采用基因交換算子，并且只對同屬于一輛車服務(wù)的客戶進(jìn)行局部搜索。

（1）初始化相關(guān)參數(shù)。種群規(guī)模popsize，最大遺傳代數(shù) maxgen，移位概率ps，倒位概率pi，變異概率pv，TS算法中禁忌表長度tslen，迭代搜索中保留的最好候選解個(gè)數(shù)bestnum；最大迭代步數(shù)tsloop；

（2）生成初始種群；

（3）解碼并計(jì)算適應(yīng)度值；

（4）按照適應(yīng)度值，由精英保留和輪盤賭進(jìn)行選擇；

（5）按照移位概率ps移位操作；

（6）按照倒位概率pi倒位操作；

（7）按照變異概率pv變異操作；

（8）令p＝1；

（9）若是p＜=popsize，執(zhí)行（10），否則轉(zhuǎn)（19）；

（10）若是rand＜=Pts，執(zhí)行（11）進(jìn)行TS局部優(yōu)化；否則轉(zhuǎn)（18）；

（11）按照解碼后染色體，將每輛車服務(wù)的客戶點(diǎn)數(shù)，隨機(jī)生成初始解，同時(shí)置空禁忌表；

（12）令k=1；

（13）若是k＜=tsloop，執(zhí)行（14），否則執(zhí)行（17）；

（14）利用交換算子對當(dāng)前解產(chǎn)生鄰域解，同時(shí)確定候選解個(gè)數(shù)為bestnum；

（15）判斷候選解滿足特赦準(zhǔn)則與否。若成立，將其替換當(dāng)前最好解；否則加入禁忌表，并解禁最早進(jìn)入禁忌表的對象；

（16）令k=k+1，執(zhí)行（13）；

（17）將TS局部優(yōu)化后子路徑編碼組成新染色體；

（18）令p=p+1，執(zhí)行（9）；

（19）gen=gen+1；

（20）若是gen＜=maxgen，則執(zhí)行（3），開始下一代PGATS操作；否則停止迭代，輸出最優(yōu)解，即最優(yōu)車輛路徑。

3　試驗(yàn)及結(jié)果分析

由物流公司的一次配送服務(wù)對模型及算法進(jìn)行驗(yàn)證。通過本文的OVRP模型，優(yōu)化配送路徑，降低配送成本。坐標(biāo)為（50，50）的配送中心為10個(gè)客戶服務(wù)，其中所租車輛固定成本為240元/輛，最大載重量為8t，最大行駛距離為250km，行駛速度為50km/h，單位距離行駛成本為20元/h。員工正常上班勞動(dòng)成本為25元/h，加班勞動(dòng)成本為40元/h，如果車輛早于時(shí)間窗的最早時(shí)間到達(dá)客戶，則等待成本為30元/h，車輛晚于時(shí)間窗的最晚時(shí)間到達(dá)客戶，則懲罰成本為50元/h。算法的參數(shù)設(shè)置和客戶信息見表1與表2。

表1　參數(shù)設(shè)置

表2　客戶信息

表3　運(yùn)行結(jié)果對比

圖4　最短路徑收斂圖

4　結(jié)語

本文對帶時(shí)間窗的車輛路徑問題進(jìn)行了擴(kuò)展，增加了工作人員的加班成本。在此情況下，建立以配送成本最小為目標(biāo)的OVRP模型，并提出了一種將單親遺傳和禁忌搜索混合的優(yōu)化算法對模型求解，同時(shí)與單親遺傳算法的運(yùn)行結(jié)果進(jìn)行比較，表明算法是可行和有效的。

［1］Brando J.A tabu search for the open vehicle routing problem［J］.European Journal of Operational Research，2004，157（3）：552-564.

［2］鐘石泉，杜綱，賀國光.有時(shí)間窗的開放式車輛路徑問題及其遺傳算法［J］.計(jì)算機(jī)工程與應(yīng)用，2006，34：201-2-4.

［3］李延暉，劉向．沿途補(bǔ)貨的多車場開放式車輛路徑問題及蟻群算法［J］．計(jì)算機(jī)集成制造系統(tǒng)，2008，14（3）：557-562．

［4］於世為，郭海湘，諸克軍.基于GA-TS的開放式車輛路徑優(yōu)化算法及應(yīng)用［J］.系統(tǒng)管理學(xué)報(bào)，2012，264-269.

［5］李茂軍，童調(diào)生.單親遺傳算法及其全局收斂性分析［J］.自動(dòng)化學(xué)報(bào)，1999，25（1）：68-72.

［6］李惠，蔣大奎.基于單親遺傳禁忌搜索算法的手術(shù)排程問題研究［J］.計(jì)算機(jī)應(yīng)用研究，2013，699-702.

Open Vehicle Routing Problem；Partheno-Genetic Algorithm；Tabu Search Algorithm

Partheno-Genetic Tabu Search for Open Vehicle Routing Optimization

CHEN Pi-ying1，YANG Bin2
（1.College of Information Engineering，Shanghai Maritime University，Shanghai 201306；2.Logistics Research Center，Shanghai Maritime University，Shanghai 201306）

1007-1423（2015）22-0003-05

10.3969/j.issn.1007-1423.2015.22.001

陳丕影（1989-），女，山東菏澤，碩士研究生，研究方向?yàn)樾畔⑾到y(tǒng)與電子商務(wù)

2015-04-30

2015-07-23

針對開放式車輛路徑問題，建立帶加班問題的車輛路徑模型；提出一種基于單親遺傳和禁忌搜索（PGATS）混合的優(yōu)化算法對模型求解，既能利用PGA并行計(jì)算、全局優(yōu)化的優(yōu)點(diǎn)，又能利用TS禁忌技術(shù)、局部搜索的優(yōu)點(diǎn)。PGA采用移位、倒位、變異算子對種群進(jìn)行更新，TS采用由交換算子產(chǎn)生的鄰域解對同屬于一輛車的客戶點(diǎn)進(jìn)行局部尋優(yōu)。實(shí)驗(yàn)表明，算法在解決運(yùn)輸問題方面是可行和有效的。

開放式車輛路徑；單親遺傳算法；禁忌搜索算法

楊斌（1975-），男，工學(xué)博士，教授，碩士生導(dǎo)師，研究方向?yàn)榫G色物流、物聯(lián)網(wǎng)、數(shù)據(jù)倉庫與數(shù)據(jù)挖掘

For open vehicle routing problem，first establishes a vehicle path model with overtime issues；then proposesa single parent genetic and tabu search（PGATS）hybrid optimization algorithm for solving the model，not only uses the advantages of parallel computing and global optimization of PGA，but also takes advantage of TS taboo technology and local search.PGA using the shift，inversion mutation operator to update the population，TS using neighborhood solution generated by the exchange operator to belong to the same customer point of a car for local optimization.Experimental results show that the algorithm in solving transport problems is feasible and effective.