發布時間：2020-04-11所屬分類：農業論文瀏覽：1次
摘 要： 摘要:以最小化總的旅行時間為優化目標，以單車
摘要:以最小化總的旅行時間為優化目標，以單車場、單車型、裝載能力和需求依背包拆分等為約束條件，將以往客戶需求不可拆分的條件松弛為依背包來離散拆分,建立了帶裝載能力的需求依背包拆分VRP(CVRPSDB)的單目標數學模型。設計了一個自適應禁忌搜索算法(ATSA)對模型進行求解。該算法采用了自適應懲罰機制，構建了一個多鄰域結構體，并針對客戶點與背包都設計了相應的鄰域操作算子，較好地適應了客戶需求量的離散拆分程度。經算例測試與文獻對比，驗證了所設計模型與算法的有效性。
關鍵詞:車輛路徑問題;拆分;依背包拆分;禁忌搜索算法;物流
車輛路徑問題(vehicleroutingproblem,VRP)自Dantzig[1]于1959年提出后，便引起了運籌學界和管理科學界的廣泛關注。相比于傳統手工排班計劃，采用現代優化算法[2]來優化行車路線，可降低車輛的行駛成本，有助于減少相應的碳排放量，降低對環境造成的影響。
根據客戶需求是否允許拆分配送，VRP可分為需求可拆分VRP[3](vehicleroutingproblemwithsplitdeliveries,VRPSD)和需求不可拆分VRP[1]。結合拆分方式是否是離散化的，VRPSD又可以分為需求離散拆分VRP[2](VRPwithdiscretesplitdeliveries,VRPDSD)與需求連續拆分的經典VRPSD[4]，而在實踐離散拆分配送的VRPDSD中也有多種拆分方式，如依背包拆分、依貨物特性拆分等。本文將重點針對帶裝載能力的需求依背包拆分VRP(capacitatedVRPwithsplitdeliveriesbybackpack,CVRPSDB)進行研究，并設計相應的禁忌搜索算法(tabusearchalgorithm,TSA)進行求解。
相關期刊推薦：《工業工程》(雙月刊)創刊于1998年，是由廣東工業大學主辦，中國機械工程學會協辦的期刊，國內外公開發行。本刊理論與應用結合，內容涵蓋經營戰略、決策研究、制造系統、物流系統、設施規劃、工作研究、成本分析、工程經濟、質量保障、診斷評價、信息管理、人機工程、生產組織、人力資源、組織重構等。讀者對象主要是從事工業工程理論與應用研究的科技人員、各級政府工業和經濟管理部門的決策人員、各類企業管理人員，高校師生及其他有關人員。
目前，在車輛路徑問題研究中，多約定客戶需求只能由一輛車一次完成，屬于需求不可拆分VRP。Dror等[3]于1989年首次提出了VRPSD的一種最基本類型，即純送貨的需求可拆分VRP(vehicleroutingproblemwithsplitdeliveries,VRPSD)，并給出了VRPSD的定義，指出對客戶需求進行合理地拆分配送有利于降低配送成本，其隨后于1994年證明了VRPSD屬于NP-hard問題[4]，并給出了VRPSD的子回路消去約束。這些研究吸引了一批學者進入可拆分VRP領域，如Archetti等[5-6]在Dror的基礎上，進一步簡化降低了VRPSD的研究難度，通過將車輛裝載能力和客戶需求予以整數單元化，假設客戶需求可按照計量單位來任意連續拆分，車輛裝載能力不小于客戶需求，構建了經典VRPSD的整數規劃模型(K-VRPSD模型)。
VRPSD拆分裝配具有理論上的成本節約性，不過在有些情況下，任意連續拆分VRPSD方式也會給物資裝配帶來實踐操作上的困難[7-8]，如將同一種物資拆分進入不同的車輛線路，這必然會給裝貨和收貨帶來不必要的麻煩。在物流配貨中，客戶的需求常可視為由一定項數的物資離散組合而成，當每項物資的特性差異很大時，配送企業可將每項物資視為一個獨立的“背包”打包用于裝配，同一個“背包”內的物資一般不適合再進行拆分組裝。如在電商物流配送、連鎖超市配送、快遞收發中由于各客戶的需求物品種類、體積大小、質量規則等都不同，其需求若拆分則適合按照“背包”來離散進行，不能按照物資重量來連續拆分。因此，研究需求依背包拆分VRP(VRPwithsplitdeliveriesbybackpack,VRPSDB)具有較強的實踐價值。另外，在VRPSD相關文獻中，除Gulczynski等[2]、Xiong等[9]、Wang等[10]、Salani等[7]、Xia等[8]的研究涉及離散拆分思想外，其余多數沿用Archetti等[5-6]構造K-VRPSD模型時采用的需求連續拆分思想。可見，對需求依背包來離散拆分的VRP進行研究具有較強的理論價值。
需求可拆分VRP(VRPSD)屬于NP-hard問題。借用Archetti等[5-6]的需求連續拆分K-VRPSD模型，謝毅[11]、劉旺盛[12]都對經典VRPSD的求解算法進行了研究。VRPSD求解難度比傳統VRP更大，而精確算法如分支定界法[4]、割平面法[13]、動態規劃法[14]、聚類−路徑兩階段法[15]、列生成及切面法[16]、分支−切平面法[17]等都只能有效求解中小規模問題，因此設計能夠解決大規模問題的智能啟發式算法(智能算法)是求解的關鍵。已有文獻在求解VRPSD及其衍生類型時主要結合了禁忌搜索算法[10-11,18-20]、遺傳算法[21]、蟻群算法[22]、蜂群算法[23]等智能優化算法。禁忌搜索算法[24-25](tabusearchalgorithm,TSA)具有簡單性、適應性、易操作性等優點，是一種求解需求可拆分VRP較為高效的智能優化算法。因此，本文也采用禁忌搜索算法來進行求解。
在以往的需求可拆分VRP文獻[5]中，對帶裝載能力的VRPSD(capacitatedVRP,CVRP)研究較多。因此，本文也對帶裝載能力的需求依背包拆分VRP(capacitatedVRPwithsplitdeliveriesbybackpack,CVRPSDB)進行研究。由于本文的CVRPDSD是依“背包”來對客戶點的需求量進行離散拆分操作，因此，CVRPSDB既是需求可拆分VRP(VRPSD)中存在的一種按“背包”離散拆分情形，也是以往傳統VRP的一種拓展。本文將以物流配送中單車場、單車型的純送貨為背景來對CVRPSDB進行建模，并設計一個自適應TSA(adaptiveTSA,ATSA)求解。
1問題描述與建模
本文的CVRPSDB可描述為：確定一系列同車型的車輛在客戶點之間的行駛順序，使其從車場出發，有序地對各客戶點進行送貨服務，最后返回原出發點，并在滿足車輛裝載能力的條件下最小化總的旅行時間。而且，各客戶點的需求量可拆分由多輛車來共同完成，但若拆分則只能按照“背包”來離散進行，其中“背包”在本文的含義為不可進一步拆分的客戶需求的最小集合。結合一般CVRP，本文的CVRPSDB有如下假設。
1)車場：車場為單車場，位置已知，且車輛數充足。
2)車輛：車輛為單車型，即全部車輛擁有相同裝載能力，約定車輛不可超載，車輛的行駛速度相同，且每條線路有截止期限限制，行駛線路為閉合式[38]，即必須返回原出發點。
3)客戶：全部客戶的地理位置、需求量已知，每個客戶需求可由多輛車依背包拆分送達，客戶點間的旅行時間符合三角不等式約束。
4)道路：忽略道路交通帶來的影響，車場到客戶點、客戶點與客戶點之間都可直達。5)目標：最小化總的旅行時間。
2自適應TSA設計
禁忌搜索算法(TSA)是一種求解VRP效果較好的智能算法。Fu等[26]對帶裝載能力約束的不拆分開放式VRP進行了求解，其研究表明，在求解算法中接受部分不可行解，能夠增強算法鄰域搜索的柔性，有利于從不可行解過渡到更好的可行解，可增強算法的全局尋優能力。本文設計一種雙優化解機制，每次迭代后保存相應的“最好解”和“當前解”，約定“最好解”必須可行，而“當前解”則可接受違反裝載能力約束的鄰域解。因此，本文在TSA搜索進程中有限的接受部分不可行解，并增設一種自適應懲罰機制，使得算法能夠在迭代過程中自適應地調整搜索方向，增強自適應尋優能力，從而形成一個自適應TSA。
2.1解的表達方式與初始解構造
本文采用隨機方式[26]生成初始可行解，先隨機生成客戶點的一個排列，然后在滿足車輛裝載能力的情況下，按照此排列順序將客戶點所對應的背包依次加入車輛線路中，當違背車輛裝載能力限制時就開啟一條新的車輛線路。其中，在構造初始可行解時，不考慮拆分，即同一客戶的背包全部放入一條線路中。
2.2多鄰域結構體設計
在大規模配送CVRPSDB中，組合情況特別復雜，其解空間非常龐大。設計多鄰域結構體，對解空間進行鄰域劃分，采用不同的局部極值來逐步逼近全局最優解是一種很好的迭代尋優方式。隨機鄰域挑選策略能夠有助于算法在各鄰域之間自由變換，加速算法尋優。X0X0=50+N
因此，ATSA設計一個多鄰域結構體，設計4種鄰域操作算子，并采用隨機鄰域變換策略，每次隨機選出一種鄰域算子對當前解變換。約定每次生成鄰域解的數目為，取。每次生成鄰域解時，采用隨機方式挑選出2條相異的線路R1與R2，然后采用隨機挑選方式，在兩線路內各挑選出一個非0的客戶點或“背包”來進行操作。每次鄰域操作后，逢多個0相鄰則只保留最前面的一個，將同一線路內的同一客戶點的“背包”按照前后順序排列在一起(即同一線路內背包合并)，并對相關約束進行檢驗，判斷生成的新鄰域解是否可行。
在本文的CVRPSDB中，結合各“背包”與其相應客戶點的對應關系，對客戶點與“背包”進行統一操作，針對“客戶點”和“背包”都設計相應的鄰域操作算子，盡可能地降低了由于訂單規模增大引發的求解難度。其中的“客戶點”鄰域操作算子相當于對同一客戶點的“背包”實施了綁定策略，而“背包”鄰域操作算子則相當于對同一客戶點的需求量施行了離散拆分策略。本文針對“客戶點”和“背包”都設計了相應的鄰域操作算子，能夠較好地適應CVRPSDB的鄰域變換。
2.4禁忌表設計與迭代終止條件
禁忌表的結構與禁忌對象選取是TSA設計的重點。TSA中禁忌長度的類型與大小對算法性能影響很大，為防止算法前期的循環搜索和增強算法中后期的隨機多樣性，本文ATSA把固定值的禁忌長度和隨機值的禁忌長度相結合，設計一個混合禁忌長度：在算法迭代尋優的前2000步內，為定值16，在2000步以后，每次迭代都在[5,16]內隨機取。N×Nςςς≤0
ATSA設置一個階的方陣式禁忌表，選取鄰域變換中的點對(i，j)作為禁忌對象，表內的矩陣元素(i，j)用于存儲禁忌對象的禁忌長度值。當點i與j或其對應的“背包”被挑選用于鄰域變換，且其對應的候選解將成為下次迭代的“當前解”時，便在其對應的矩陣元素(i，j)中填入對應的值。本文約定在每次鄰域變換后減1，直到方可解除對相應解的禁忌。若存在某個可行“候選解”優于當前取到的“最好解”，則把其設置為新的“當前解”與“最好解”，否則將非禁忌的最佳候選解置換為新的當前解;若全部“候選解”都被禁忌了，則釋放最佳“候選解”，并將其設為新的當前解。為了增強算法全局尋優能力，防止因禁忌過度而漏搜了有關解集區域，本文增設一個“禁忌表重新初始化”策略，約定在迭代2000步以后，每隔m次迭代就將禁忌表重新初始化為全0矩陣，m=50。X1X1=5000+100N終止迭代的條件為：總迭代次數達到預設的上限值，本文取。
2.5算法描述依據禁忌搜索算法的基本框架，ATSA的基本流程如下。
Step1 初始化;
Step2 讀入相關數據及參數值;
Step3 隨機生成初始解，并把此解取為“最好解”與“當前解”;
Step4While未滿足總迭代次數do;
Step5While候選解數目未達到預設值do;
Step6 在預設的4種鄰域操作算子之間隨機挑選出一種用于鄰域變換;
Step7 按規則對“當前解”進行鄰域變換，并構建候選解集;
Step8End;
Step9 挑選出新的“最好解”與“當前解”;
Step10 更新禁忌表;
Step11End;
Step12 輸出結果。
3算法測試
3.1算例構造
需求依背包拆分VRP(VRPSDB)目前尚未有標準測試算例。文獻[12]、[22]、[23]在研究經典CVRPSD時，都采用一個含1個配送中心、15個客戶點、客戶需求總和為4881、車輛載重為500的CVRP算例進行了算法測試。因此，本文在該算例基礎上構造CVRPSDB算例，并將其標記為CVRPSDB-15。將算例中各客戶點的需求拆分為1~4個背包，這樣便構造出了CVRPSDB的算例CVRPSDB-15，其客戶需求數據如表1所示。
3.2求解結果
本文使用的編程軟件為Matlab2014a，并且在Lenovo3000，CPU為2.40GHz，內存為4GB的AMD筆記本上測試ATSA。運行20次，取最好的結果。
求解結果顯示，CVRPSDB-15的總行駛距離為1720.8，有2個客戶點的需求量被依背包離散拆分配送，具體求解結果如表2所示。其中，客戶點5的需求量被依背包拆分進入線路4與線路10中，對應的離散拆分量分別為(71)與(64+90);而客戶點14的需求量被依背包拆分進入線路1與線路6中，對應的離散拆分量分別為(136)與(22+143+161)。
3.3文獻對比分析
ATSA與文獻算法的對比結果見表3。表3中給出的聚類求解算法、改進蟻群算法與蜂群優化算法都是用來求解經典K-VRPSD類型的，文獻[23]給出的傳統VRP算法是用來求解需求不拆分VRP類型的。從求得的結果來看，本文算法求解的結果比4種對比算法求得的結果都要優，ATSA相對于聚類求解算法、改進蟻群算法、蜂群優化算法和傳統VRP算法分別改進了2.53%、3.38%、2.43%和15.64%，這說明ATSA在降低車輛旅行時間方面具有優勢。
4結論
帶裝載能力的需求依背包拆分VRP是一種新類型的VRP。從本文研究可知，對客戶需求依背包進行離散拆分配送，既方便了拆分配貨，又有助于縮短旅行時間，降低行駛成本。本文結合相關約束給出了對應的數學模型，并設計了一種自適應禁忌搜索算法(ATSA)進行求解。從測試結果來看，所設計的ATSA在降低行駛成本方面具有較強的能力。另外，在算法中嵌入自適應懲罰機制，設計多鄰域結構體，采用隨機鄰域挑選方式，使用混合禁忌長度，增設禁忌表重新初始化策略等能夠提升算法的爬山能力，增強尋優能力。不過，本文主要對純送貨類型的CVRPSDB及其自適應禁忌搜索算法進行了研究，而逆向物流VRP在實踐中也是急需解決的難題。因此，后續將會對同時取送貨類型的CVRPSDB進行研究，并設計出更為高效的求解算法。
SCISSCIAHCI
