帶雙時間窗約束的糧食專用車調度優化

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

摘要：

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

關鍵詞：

糧食專用車; 雙時間窗; 優化模型; Gurobi求解

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

文獻標志碼：? 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 引 言

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

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

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

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

1 問題描述

已知糧食專用車的類型、客戶與港口之間的距離、客戶所需運輸的貨量、鐵路規定的港口與客戶間線路的硬時間窗、客戶的軟時間窗、隨運輸距離發生變化的運價等，為得到每一車皮組服務客戶的選擇以及服務的順序，以港口經營糧食專用車的收入最高和糧食專用車平均運行時間最短為雙目標，以加權的方式將雙目標轉化為求單目標的最大值，對雙時間窗約束的糧食專用車車輛調度進行優化，確定哪組車皮為哪家客戶服務，以及服務順序、去程時間段和返程時間段。

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

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

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

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

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

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

2 模型設計

2.1 模型假設與符號定義

通過調查，對模型作如下假設：①糧食專用車每節車皮的最大裝載量為60 t;

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

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

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

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

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

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

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

⑨根據實際的客戶需求將列車車型

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

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

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

2.2 模型建立

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

式（1）～（16）中各參數下標的范圍如下：

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

2.3 模型的改進

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

步驟1

求解各個單目標條件下的最優值。f1、f2均用C#調用Gurobi求解，f1在本模型中為式（1），f2在本模型中為式（2）。

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

步驟3

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

因此，新目標函數為

3 算例分析

3.1 應用數據

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

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

3.2 模型求解

經過改進不難看出，雙時間窗約束下的糧食專用車調度優化模型屬于雙目標整數線性規劃模型，可以用C#調用Gurobi結合啟發式算法進行求解。模型求解步驟如下：

步驟1

由于兩個目標函數的量綱不一致，在

用Gurobi求解之前需要對目標函數進行標準化處理。采用極值化方法，讓兩個目標函數除以各自目標函數的最大值。

步驟2

求解兩個目標函數各自的權重，結果如下：

α1=0.14， α2=0.86

步驟3

改進目標函數，用H表示兩個目標綜合的結果：

Hmax=0.14Rmax-0.86Tminj i k xkij

步驟4

利用C#調用Gurobi進行求解，輸出的最終結果為8 071 133.92。這個數據表示的是一個綜合的結果——在糧食專用車周轉率最高的情況下使得港口經營糧食專用車的收入最高。

3.3 結果分析

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

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

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

結果表明，運用優化模型進行糧食專用車調度能夠使港口收入明顯增加，并提高糧食專用車的周轉率。

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

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

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

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

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

4 結 論

糧食專用車在鐵路糧食運輸的過程中發揮著重要作用，結合當前我國北方某港口現狀，本文提出以港口

經營

糧食專用車的收入最高和糧食專用車周轉率最高為目標的帶時間窗的車輛調度問題，建立了混合整數規劃模型，并用C#調用Gurobi求解算例。結果表明，本文所構建的混合整數規劃模型是可行且有效的。

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

參考文獻：

[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，FU 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]李秀娟， 楊玥， 蔣金葉， 等. 蟻群優化算法在物流車輛調度系統中的應用[J]. 計算機應用， 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]韓廣， 李雪楊， 孫曉云， 等. 鐵路行車調度問題的改進粒子群優化研究[J]. 控制工程， 2017， 24（9）： 1855-1859. DOI： 10.14107/j.cnki.kzgc.b1.0277.

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

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

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

[11]任蘋， 李楠， 高立群. 基于集成粒子群優化的復線旅客列車優化調度[J]. 系統仿真學報， 2007， 19（7）： 1449-1452. DOI： 10.3969/j.issn.1004-731X.2007.07.011.

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

[13]姜世臣. 大連港散糧碼頭公司糧食專用車調度優化研究[D]. 大連： 大連海事大學， 2017.

[14]辛曉剛， 王彪， 李昕， 等. 考慮風電消納能力的含風電場電力系統多目標優化調度研究[J]. 可再生能源， 2016， 34（1）： 49-55. DOI： 10.13941/j.cnki.21-1469/tk.2016.01.008.

（編輯 賈裙平）