帶雙時間窗約束的糧食專用車調(diào)度優(yōu)化

唐麗敏　張雅茹　潘相君　張殿勇

摘要：

針對港口企業(yè)經(jīng)營的糧食專用車調(diào)度問題，在傳統(tǒng)的車輛調(diào)度問題上新增雙時間窗約束，以糧食專用車周轉(zhuǎn)率最大和港口企業(yè)經(jīng)營糧食專用車的收入最大為目標(biāo)建立雙目標(biāo)規(guī)劃模型，并用算例驗證模型和算法的有效性。結(jié)論如下：在運量與運距相矛盾的情況下，優(yōu)先選擇距離近、運量小的客戶進行服務(wù)。此研究能夠為糧食專用車調(diào)度決策提供參考。

關(guān)鍵詞：

糧食專用車; 雙時間窗; 優(yōu)化模型; Gurobi求解

中圖分類號：? U294.1+2; U294.8+91

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

Scheduling optimization of special vehicles for grain

with double time window constraint

TANG Limin1， ZHANG Yaru1， PAN Xiangjun1， ZHANG Dianyong2

（1. College of Transportation Engineering， Dalian Maritime University， Dalian 116026， Liaoning， China;

2. Yantai Port Co.， Ltd.， Yantai 264000， Shandong， China）

Abstract：

Aiming at the scheduling problem of special vehicles for grain operated by port enterprises， the double time window constraint is added to the traditional vehicle scheduling problem， and the two-objective programming model is established with the objectives of the maximum turnover rate of special vehicles for grain and the maximum income brought by port enterprises to operate special vehicles for grain. The validity of the model and the algorithm is verified by examples. The conclusion is as follows： in the case of contradiction between transportation volume and transportation distance， customers with close distance and small transportation volume are preferred to serve. This research can provide reference for the scheduling decision of special vehicles for grain.

Key words：

special vehicle for grain; double time window; optimization model; Gurobi solving

收稿日期： 2020-06-08

修回日期： 2020-09-22

作者簡介：

唐麗敏（1963—），女，遼寧大連人，教授，博士，研究方向為交通運輸工程，（E-mail）tlmin@dlmu.edu.cn

0 引 言

“北糧南運”是我國糧食物流的主要特征。為促進散糧高效運輸，糧食碼頭或糧食物流企業(yè)備有鐵路糧食專用車（以下簡稱“糧食專用車”）。糧食專用車的調(diào)度受到鐵路和貨主時間的限制，若在此雙時間窗約束下實現(xiàn)對糧食專用車的合理調(diào)度，對提高糧食專用車周轉(zhuǎn)率具有重要意義。

車輛調(diào)度的核心問題是車輛路徑問題（vehicle routing problem，VRP）。1959年DANTZIG等[1]首次提出VRP，并給出一個基于線性規(guī)劃的近似最優(yōu)解的求解方法。很多學(xué)者為更快捷地得出較為精確的車輛調(diào)度方案，根據(jù)不同場景做了一系列研究，具體表現(xiàn)在對各種啟發(fā)式算法的改進上：QIU等[2]面對分散的客戶需求，提出具有特殊設(shè)計的數(shù)學(xué)模型和禁忌搜索算法，并通過對比證明該方法的優(yōu)越性;LIAO等[3]在調(diào)度作業(yè)中加入對時間序列加權(quán)時滯的考慮，提出一種單機環(huán)境下具有競爭性的蟻群優(yōu)化算法;胡云清[4]設(shè)計了適用于VRP求解的模擬退火算法，并提高了該算法的求解性能;李秀娟等[5]根據(jù)物流車輛調(diào)度系統(tǒng)自身和蟻群算法的特點，對蟻群算法進行了改進。隨著研究的進一步深入，一些學(xué)者開始研究帶時間窗的車輛路徑問題[6]（vehicle routing problem with time windows ，VRPTW），如韓廣等[7]針對VRPTW提出一種改進的粒子群優(yōu)化算法，解決了普通粒子群優(yōu)化算法收斂慢和精確度低的問題。部分學(xué)者結(jié)合多目標(biāo)模型研究VRPTW：郭小樂等[8]針對高鐵站公交時刻表與車輛調(diào)度綜合問題，建立多目標(biāo)綜合優(yōu)化模型，并設(shè)計遺傳算法求解;龐燕等[9]建立了車輛最少和路程最短的雙目標(biāo)模型，并改進了兩階段禁忌搜索算法;范厚明等[10]為提高種群的多樣性，設(shè)計了適合求解多目標(biāo)VRP的混合遺傳算法。鐵路方面的車輛調(diào)度研究主要是從降低成本和提高客戶滿意度（即減少等待時間）等方面進行的，如任蘋等[11]建立了多種旅客列車期望時間和運行時間最短的多目標(biāo)模型，運用集成粒子群優(yōu)化算法解決優(yōu)化調(diào)度問題。

綜上，既有文獻(xiàn)對帶時間窗的車輛調(diào)度模型和算法做了很多改進，但很少將其直接運用在鐵路上[12]。文獻(xiàn)[13]成為僅有的將車輛調(diào)度運用到糧食專用車上的文獻(xiàn)。與道路車輛調(diào)度問題不同的是，港口或糧食物流企業(yè)擁有的糧食專用車在利用鐵路進行糧食運輸時，面臨來自客戶和鐵路兩方面的時間窗約束，加上鐵路運輸在一定時間內(nèi)的容量限制，僅憑經(jīng)驗進行糧食專用車的調(diào)度，不僅達(dá)不到糧食專用車的高效周轉(zhuǎn)，而且可能增加額外成本。因此，糧食專用車調(diào)度問題具有硬時間窗限制的特殊之處。

為解決糧食專用車調(diào)度問題，本文考慮鐵路規(guī)定的硬時間窗和客戶所規(guī)定的軟時間窗的雙重約束，建立混合整數(shù)規(guī)劃模型。該模型以港口經(jīng)營糧食專用車的收入最高和糧食專用車平均運行時間最短為目標(biāo)，并考慮同一鐵路線同一時間段所容納車皮組數(shù)和同一車皮組前后服務(wù)時間的約束。設(shè)置“糧食專用車平均運行時間最短”的目的是讓糧食專用車在周期內(nèi)運轉(zhuǎn)次數(shù)最多，即周轉(zhuǎn)率最高。

1 問題描述

已知糧食專用車的類型、客戶與港口之間的距離、客戶所需運輸?shù)呢浟?、鐵路規(guī)定的港口與客戶間線路的硬時間窗、客戶的軟時間窗、隨運輸距離發(fā)生變化的運價等，為得到每一車皮組服務(wù)客戶的選擇以及服務(wù)的順序，以港口經(jīng)營糧食專用車的收入最高和糧食專用車平均運行時間最短為雙目標(biāo)，以加權(quán)的方式將雙目標(biāo)轉(zhuǎn)化為求單目標(biāo)的最大值，對雙時間窗約束的糧食專用車車輛調(diào)度進行優(yōu)化，確定哪組車皮為哪家客戶服務(wù)，以及服務(wù)順序、去程時間段和返程時間段。

本文提到的一個車皮組指的是一組車皮（也稱一列車皮），例如

車皮組A1指的是車型為A的第1組車皮;車皮數(shù)指的是一個車皮組中車皮的數(shù)量，例如車皮組A1的車皮數(shù)為40指的是車型為A的第1組車皮共有40節(jié)車皮;車皮組數(shù)指的是車皮組的數(shù)量。

本文提到的鐵路規(guī)定的硬時間窗限制是港口糧食專用車服務(wù)某個客戶的去程和返程所經(jīng)過鐵路線的時間窗限制，這個時間窗限制是必須滿足的?？蛻鬸的第t個和第r個時間段是指在一定周期內(nèi)，港口與客戶之間鐵路線開放的第t個和第r個時間段，其中t是糧食專用車從港口去往客戶j選擇的時間段，r是糧食專用車從客戶j返回港口選擇的時間段。每個客戶選擇的每個鐵路開放時間段都是獨立的，不受其他客戶所選擇的鐵路開放時間段的影響，例如：客戶1選擇的第一個鐵路開放時間段可以晚于客戶2選擇的第二個鐵路開放時間段。

圖1是糧食專用車服務(wù)客戶的往返示意圖，包括去程和返程。

圖2是模擬一個車皮組為客戶服務(wù)的狀態(tài)，同一車皮組在一個時間段內(nèi)只能為一位客戶服務(wù)，而且同一車皮組必須在一位客戶處裝車完畢返回港口并卸車完畢后才能為另外一位客戶

服務(wù)。假設(shè)該車皮組選擇客戶1的第t個時間段從港口出發(fā)，到達(dá)客戶1所在地并裝載完畢后，選擇客戶1的第r（r>t）個時間段返回港口;若卸車后客戶2有需求，則該車皮組重新出發(fā)，為客戶2提供服務(wù)。在此過程中，每次去程和返程均必須嚴(yán)格滿足港口與此客戶之間鐵路線的時間段限制，也就是說即使車皮已經(jīng)全部裝車完畢或者全部卸車完畢也必須等到此線路的硬時間窗開啟才能出發(fā)。

2 模型設(shè)計

2.1 模型假設(shè)與符號定義

通過調(diào)查，對模型作如下假設(shè)：①糧食專用車每節(jié)車皮的最大裝載量為60 t;

②對于擁有糧食專用車的港口來說，向客戶收取的租車費用按每節(jié)車皮的最大裝載量計算;

③鐵路給出的時間窗均大于糧食專用車從港口到客戶（或從客戶返回港口）所需的時間;

④根據(jù)鐵路線的規(guī)定，同一時間在同一條線路（從港口至同一個目的地的線路視為一條線路）上的車皮組數(shù)有一定限制;

⑤以30 d（即720 h）為一個決策周期;

⑥不考慮固定成本、折舊成本和裝卸時間;

⑦每段通行均在給出的時間段的開始時刻出發(fā)，若在一個時間段的中間某時刻裝車完畢或者卸車完畢，則必須等待下一個時間段開始才能出發(fā);

⑧每個客戶在其軟時間窗開啟之前都已經(jīng)備好貨;

⑨根據(jù)實際的客戶需求將列車車型

分為A、B、C等3種，這3種車型的車皮數(shù)分別為[30，40]、[40，50]、[50，60]。

定義模型參數(shù)如下：R為港口經(jīng)營糧食專用車獲得的收入;T為糧食專用車運行時間;O為港口集合，o∈O;K為車型集合，k∈K;I為車皮組的編號集合，i∈I;J為客戶集合，j∈J;ki為車型為k的第i個車皮組;Nki為車型為k的第i個車皮組的車皮數(shù);Doj為糧食專用車從港口o到客戶j的運行時間;qj為客戶j的貨量;Voj為糧食專用車從港口o到客戶j的運價（越遠(yuǎn)越低）;[Bj，Ej]為客戶j允許服務(wù)的時間窗;[bojm，eojm]為港口o與客戶j之間鐵路開放的第m個時間窗，m∈M;t和r分別為糧食專用車從港口到客戶和從客戶到港口選擇的客戶鐵路線的時間窗編號， t，r∈M;Cki為車型為k的第i個車皮組的裝卸車費用;hj為與客戶j軟時間窗相關(guān)的懲罰系數(shù)。

定義決策變量為：xkij，若車型為k的第i個車皮組為客戶j服務(wù)，則xkij=1，否則xkij=0;ykiojt，若車型為k的第i個車皮組從港口o出發(fā)為客戶j服務(wù)，并選擇客戶j鐵路線的第t個硬時間窗，則ykiojt=1，否則ykiojt=0;wkijor，若車型為k的第i個車皮組從客戶j返回港口o，并選擇客戶j鐵路線的第r個時間窗，則wkijor=1，否則wkijor=0。

2.2 模型建立

所考慮的問題可以用兩個混合整數(shù)規(guī)劃模型描述，其目標(biāo)分別是使港口經(jīng)營糧食專用車的收入最高和糧食專用車平均運行時間最短。模型如下：

式（1）～（16）中各參數(shù)下標(biāo)的范圍如下：

i，i′∈I，i≠i′; k，k′∈K，k≠k′; j，j′∈J，j≠j′

t′，t∈M，t≠t′;r，r′∈M，r≠r′;r≥t+1

式（1）表示模型目標(biāo)為港口經(jīng)營糧食專用車的收入最高，收入包括糧食專用車出租費用和裝卸費用，但要減去因開始為客戶服務(wù)的時間晚于客戶規(guī)定的時間而產(chǎn)生的懲罰費用;式（2）表示模型目標(biāo)為糧食專用車平均運行時間最短，平均運行時間最短是為了使周轉(zhuǎn)率最高。平均運行時間等于所有的車皮組服務(wù)客戶所花費的總時間與所服務(wù)的客戶總數(shù)的商，總時間包括往返路上耗費的時間和在客戶處停留的時間;式（3）表示每個客戶至少被服務(wù)一次;式（4）表示在不浪費資源的條件下，每一車皮組至少為一位客戶服務(wù);式（5）和（6）表示車型為k的第i個車皮組為客戶j服務(wù)，去程和返程時間均需滿足客戶j的時間窗約束;式（7）和（8）表示在同一時間段內(nèi)港口與某一客戶之間鐵路線上的車皮組數(shù)應(yīng)小于鐵路線的最大承受能力;式（9）表示在某一車皮組為某一客戶服務(wù)的過程中，車皮組從港口出發(fā)在客戶的某一時間段到達(dá)客戶所在地，就必須在此客戶的另一時間段從客戶處出發(fā)返回港口;式（10）表示在客戶j的時間段順序中，上一車皮組為其服務(wù)返回港口之后下一車皮組才能出發(fā);式（11）表示在時間順序中，某一車皮組如果之前為某一客戶服務(wù)，就必須在從此客戶處返回港口之后才能再次出發(fā)為同一客戶或其他客戶服務(wù);式（12）表示某一車皮組同一時間只能服務(wù)一位客戶;式（13）表示為某一客戶服務(wù)的車皮組數(shù)的限制;式（14）～（16）表示決策變量的限制。

2.3 模型的改進

為便于求解，對模型進行改進[14]，步驟如下：

步驟1

求解各個單目標(biāo)條件下的最優(yōu)值。f1、f2均用C#調(diào)用Gurobi求解，f1在本模型中為式（1），f2在本模型中為式（2）。

步驟2 將多目標(biāo)轉(zhuǎn)化為單目標(biāo)求解。由于模型中兩個目標(biāo)的量綱不一致，所以需要對其進行標(biāo)準(zhǔn)化處理。令標(biāo)準(zhǔn)化函數(shù)F1=f1/f″1，F(xiàn)2=f2/f″2，其中f″1、f″2分別為f1、f2的最大值，此時F1、F2的值域均為[0，1]。

步驟3

用線性加權(quán)和法求權(quán)重[12]。令F=α1F1-α2F2，其中α1、α2由下列方程組確定：

因此，新目標(biāo)函數(shù)為

3 算例分析

3.1 應(yīng)用數(shù)據(jù)

以我國北方某港口及其客戶（12位）信息為基礎(chǔ)，設(shè)計算例。算例數(shù)據(jù)見表1。

另外，A、B、C型糧食專用車每節(jié)車皮的裝卸費用分別為2 000元、2 500元、3 000元。

3.2 模型求解

經(jīng)過改進不難看出，雙時間窗約束下的糧食專用車調(diào)度優(yōu)化模型屬于雙目標(biāo)整數(shù)線性規(guī)劃模型，可以用C#調(diào)用Gurobi結(jié)合啟發(fā)式算法進行求解。模型求解步驟如下：

步驟1

由于兩個目標(biāo)函數(shù)的量綱不一致，在

用Gurobi求解之前需要對目標(biāo)函數(shù)進行標(biāo)準(zhǔn)化處理。采用極值化方法，讓兩個目標(biāo)函數(shù)除以各自目標(biāo)函數(shù)的最大值。

步驟2

求解兩個目標(biāo)函數(shù)各自的權(quán)重，結(jié)果如下：

α1=0.14， α2=0.86

步驟3

改進目標(biāo)函數(shù)，用H表示兩個目標(biāo)綜合的結(jié)果：

Hmax=0.14Rmax-0.86Tminj i k xkij

步驟4

利用C#調(diào)用Gurobi進行求解，輸出的最終結(jié)果為8 071 133.92。這個數(shù)據(jù)表示的是一個綜合的結(jié)果——在糧食專用車周轉(zhuǎn)率最高的情況下使得港口經(jīng)營糧食專用車的收入最高。

3.3 結(jié)果分析

為便于分析，將模型求解結(jié)果列于表2中。由表2可知，無論是哪個車皮組，均先服務(wù)完一個客戶后再服務(wù)另外一個客戶，服務(wù)過程遵循港口與客戶之間鐵路線的硬時間窗要求。

以糧食專用車第1次為客戶1服務(wù)為例解讀表2：客戶1第一次被車型為A的第4個車皮組服務(wù)，所選擇的去程和返程硬時間窗編號分別為1和2。對照表1可知，糧食專用車從港口到客戶1選擇的時間窗為[3，40]，從客戶1到港口的返程時間窗為[90，135]。

本文使用同樣的方法，單獨求解標(biāo)準(zhǔn)化函數(shù)F2的最小值，將求得的車輛調(diào)度方案代入標(biāo)準(zhǔn)化函數(shù)F1進行求解，將兩個結(jié)果分別乘以對應(yīng)的權(quán)重，求得的結(jié)果為433 004.06;另外，單獨求解標(biāo)準(zhǔn)化函數(shù)F1的最大值，將求得的車輛調(diào)度方案代入標(biāo)準(zhǔn)化函數(shù)F2進行求解，將兩個結(jié)果分別乘以對應(yīng)的權(quán)重，求得的結(jié)果為8 075 533.10。經(jīng)過對比可知，本文使用的模型求解結(jié)果更優(yōu)。另外，糧食專用車“成列”發(fā)車點集中在規(guī)模較大的十幾個站點，本文調(diào)用Gurobi求得最終的運行時間為1 100 s，能夠應(yīng)對實際運行的要求。

結(jié)果表明，運用優(yōu)化模型進行糧食專用車調(diào)度能夠使港口收入明顯增加，并提高糧食專用車的周轉(zhuǎn)率。

通過算例分析，還能得到3點啟示：

（1）糧食專用車所掛車皮數(shù)影響糧食專用車周轉(zhuǎn)率和港口的收入。本文的算例求解結(jié)果顯示，相對于所掛車皮數(shù)為40節(jié)的糧食專用車來說，所掛車皮數(shù)為50節(jié)和60節(jié)的糧食專用車服務(wù)客戶的頻率更高。這表明在客戶有足夠運量需求的情況下港口應(yīng)在不超過最大限制的前提下，盡可能多掛車皮。

（2）港口與客戶的距離和客戶運量需求對于糧食專用車服務(wù)客戶的順序有直接影響，這也決定了糧食專用車調(diào)度方案的形式。通過算例可以看出，所掛車皮數(shù)為40節(jié)的第4個車皮組先為距離573 km、運量需求為13 000 t的客戶1服務(wù)，再為距離為1 449 km、運量需求為13 600 t的客戶10服務(wù)。在時間窗限制下，當(dāng)面對距離近、運量小和距離遠(yuǎn)、運量大的客戶時，

糧食專用車會優(yōu)先服務(wù)距離近的客戶，這樣可以有效增加一定周期內(nèi)港口的收入，并且能提高糧食專用車的服務(wù)效率。

（3）所掛車皮數(shù)較少的糧食專用車會在最后進行調(diào)配，起補充作用。通過算例結(jié)果可以看出，受運費和資源的影響，為顧客提供最后一次服務(wù)的糧食專用車所掛車皮數(shù)大多為40節(jié)。

4 結(jié) 論

糧食專用車在鐵路糧食運輸?shù)倪^程中發(fā)揮著重要作用，結(jié)合當(dāng)前我國北方某港口現(xiàn)狀，本文提出以港口

經(jīng)營

糧食專用車的收入最高和糧食專用車周轉(zhuǎn)率最高為目標(biāo)的帶時間窗的車輛調(diào)度問題，建立了混合整數(shù)規(guī)劃模型，并用C#調(diào)用Gurobi求解算例。結(jié)果表明，本文所構(gòu)建的混合整數(shù)規(guī)劃模型是可行且有效的。

從本文的糧食專用車調(diào)度方案看，在客戶運量需求較大的情況下，較為理想的是每列糧食專用車按照最大許可數(shù)量拖掛車皮。同時，面對運距不同、運量需求不同的客戶，應(yīng)在滿足客戶和鐵路時間窗的情況下，盡量先考慮運距再考慮運量。另外，在求解方面，針對目前“北糧南運”糧食專用車的發(fā)車頻率和規(guī)模，調(diào)用Gurobi運用啟發(fā)式算法求解可以達(dá)到優(yōu)化車輛調(diào)度的目的。下一步將嘗試考慮大范圍、多品種大宗物資的鐵路專用車調(diào)運問題，使模型和算法更具普遍性。

參考文獻(xiàn)：

[1]DANTZIG G B，RAMSER J H . The truck dispatching problem[J]. Management Science， 1959， 6（1）： 80-91. DOI： 10.1287/mnsc.6.1.80.

[2]QIU Meng，F(xiàn)U Zhuo， EGLESE R，et al. A tabu search algorithm for the vehicle routing problem with discrete split deliveries and pickups[J]. Computers & Operations Research， 2018， 100： 102-116. DOI： 10.1016/j.cor.2018.07.021.

[3]LIAO C J，JUAN H C. An ant colony optimization for single-machine tardiness scheduling with sequence-dependent setups[J]. Computers and Operations Research， 2007， 34： 1899-1909. DOI： 10.1016/j.cor.2005.07.020.

[4]胡云清. 求解VRP問題的混沌模擬退火螢火蟲算法[J]. 包裝工程， 2017， 38（7）： 216-221. DOI： 10.19554/j.cnki.1001-3563.2017.07.048.

[5]李秀娟， 楊玥， 蔣金葉， 等. 蟻群優(yōu)化算法在物流車輛調(diào)度系統(tǒng)中的應(yīng)用[J]. 計算機應(yīng)用， 2013， 33（10）： 2822-2826. DOI： 10.11772/j.issn.1001-9081.2013.10.2822.

[6]CHU J C，YAN Shangyao， HUANG H J. A multi-trip split-delivery vehicle routing problem with time windows for inventory replenishment under stochastic travel times[J]. Networks & Spatial Economics， 2017， 17（1）： 41-68. DOI： 10.1007/s11067-015-9317-3.

[7]韓廣， 李雪楊， 孫曉云， 等. 鐵路行車調(diào)度問題的改進粒子群優(yōu)化研究[J]. 控制工程， 2017， 24（9）： 1855-1859. DOI： 10.14107/j.cnki.kzgc.b1.0277.

[8]郭小樂， 宋瑞， 何世偉， 等. 高鐵車站接運公交時刻表與車輛調(diào)度綜合優(yōu)化[J]. 鐵道學(xué)報， 2019， 41（1）： 26-34. DOI： 10.3969/j.issn.1001-8360.2019.01.003.

[9]龐燕， 羅華麗， 夏揚坤. 基于禁忌搜索算法的廢棄家具回收車輛路徑優(yōu)化[J]. 計算機集成制造系統(tǒng)， 2020， 26（5）： 1425-1433. DOI： 10.13196/j.cims.2020.05.026.

[10]范厚明， 吳嘉鑫， 耿靜， 等. 模糊需求與時間窗的車輛路徑問題及混合遺傳算法求解[J]. 系統(tǒng)管理學(xué)報， 2020， 29（1）： 107-118. DOI： 10.3969/j.issn.1005-2542.2020.01.012.

[11]任蘋， 李楠， 高立群. 基于集成粒子群優(yōu)化的復(fù)線旅客列車優(yōu)化調(diào)度[J]. 系統(tǒng)仿真學(xué)報， 2007， 19（7）： 1449-1452. DOI： 10.3969/j.issn.1004-731X.2007.07.011.

[12]曾慶成， 于婷. 基于碼頭集卡共享的運輸任務(wù)分配優(yōu)化模型[J]. 上海海事大學(xué)學(xué)報， 2020， 41（1）： 64-70. DOI： 10.13340/j.jsmu.2020.01.011.

[13]姜世臣. 大連港散糧碼頭公司糧食專用車調(diào)度優(yōu)化研究[D]. 大連： 大連海事大學(xué)， 2017.

[14]辛?xí)詣偅?王彪， 李昕， 等. 考慮風(fēng)電消納能力的含風(fēng)電場電力系統(tǒng)多目標(biāo)優(yōu)化調(diào)度研究[J]. 可再生能源， 2016， 34（1）： 49-55. DOI： 10.13941/j.cnki.21-1469/tk.2016.01.008.

（編輯 賈裙平）