新一代信息技術背景下循環(huán)取貨路徑規(guī)劃問題

張慧，宋少忠，安毅，辛剛，鐘天擇

（1.長春汽車工業(yè)高等專科學校 信息技術學院，長春 130013；2.吉林工程技術師范學院 數(shù)據(jù)科學與人工智能學院，長春 130052；3.吉林工程技術師范學院 電氣與信息工程學院，長春 130052；4.吉林工商學院 工學院，長春 130062；5.吉林大學 管理學院，長春 130012）

0 引言

新一代信息技術在傳統(tǒng)產業(yè)轉型升級過程中起到非常重要的作用，尤其是有一定生產需求的汽車制造業(yè)，在國務院發(fā)布的《關于深化制造業(yè)與互聯(lián)網(wǎng)融合發(fā)展的指導意見》［1］政策推動下，以人工智能為代表的新一代信息技術在生產物流方面擁有了廣闊的市場空間，占據(jù)了指引城市物流發(fā)展的主導地位.其中，生產物流的體系結構是否具有科學且正確的指導性是與企業(yè)的生產效率和經(jīng)濟效益密不可分.為了提高汽車制造廠、物流管理人員和各個供應商對物流管理方法的認可度，既要有合理的路線要求、規(guī)范的運行時刻，還應當考慮高集載率來保證車輛取送貨的各方成本降低，但其方案的設計與實現(xiàn)過程是非常復雜的.循環(huán)取貨物流模式高集載率的特性可以在降低汽車廠A庫存量的同時，減少汽車零部件供應商本身的物流風險以及缺貨甚至停線的風險.

國內外研究者們嘗試使用基本的人工智能算法解決路徑規(guī)劃問題，包括禁忌搜索算法［2］、智能水滴算法［3］、遺傳算法［4］、蟻群算法［5］等.實際物流配送過程中，在滿足時間窗約束條件下，需要對生產需求量拆分和物流車輛容載量拆分，這使得如何解決城市物流的車輛路徑規(guī)劃問題也顯得越來越緊迫［6］.因而，越來越多的改進智能算法涌現(xiàn)出來，例如運用改進的蟻群算法與遺傳算法基于時間窗和送貨需求可拆分車輛路徑問題［7-8］、利用改進搜索方法通過拆分解決車輛路徑問題［9］等等.

在實現(xiàn)基礎經(jīng)濟效益的前提下，按時取貨送貨、合理分配空間也是汽車制造廠、物流管理人員和各個供應商對運輸服務的目標需求.傳統(tǒng)汽車零部件運輸過程設計要求的單一性會造成車輛集載率過度和容量浪費等問題，導致物流運輸成本沒有達到最小化.新一代信息技術的賦能使城市物流行業(yè)的此類資源浪費問題得以解決.本文以汽車廠A為例，在同城面對多目標、多車程的汽車零部件循環(huán)取貨的實際問題入手，以該廠運營需求和實際動態(tài)反饋作為依據(jù)，旨在基于人工智能和經(jīng)濟發(fā)展方面解決物流車輛路徑規(guī)劃問題，充分考慮汽車廠A的實際生產需求、其他供應商的實際生產供應量、依據(jù)汽車零部件的體積占比與物流車輛容載率之間的關系，以及參與其中的各方時間窗需求等因素，進而改進粒子群算法.

1 問題描述

在企業(yè)生產與物流管理過程中，多目標、多車程、多時間窗、多容載量的汽車零部件循環(huán)取貨路徑規(guī)劃問題是通過一個總體的物流管理中心分配若干輛不同車型的運輸車，為一個總體裝配中心和多個服務供應商提供取送貨服務，根據(jù)總體裝配中心生產所需要汽車零部件的數(shù)量、不同服務供應商提供零部件的種類和數(shù)量、不同車型運輸車的最大載重量、基于Q市智能地圖的總體裝配中心（汽車廠A）與各個供應商之間形成的拓撲結構，以及各個供應商的服務時間窗等約束條件，高集載率的循環(huán)取送貨物流模式如下：選配車輛可以為多個供應商提供運輸服務，從汽車廠A的總體裝配中心出發(fā)再回到汽車廠A的總體裝配中心是一次完整的循環(huán)取送貨過程.假設某個供應商由一輛選配運輸車輛在規(guī)定的時間窗約束條件下完成了取貨服務，當前供應商提供裝貨的時間窗固定、用每一輛配送車輛的成本和單位行駛距離成本均固定的前提下，運輸車輛仍有空間供其他供應商的汽車零部件使用時，在考慮以上約束情形下，要充分合理地規(guī)劃物流車輛的路徑，確保運輸車輛行駛的總距離和時間相對最少.

文章以Q市的45個汽車零部件供應商為例，按照計劃對不同數(shù)量的汽車零部件提出需求，即總體裝配中心向供應商客戶取回貨物，由一個車隊（包含不同車型）負責分取汽車零部件，組織適當?shù)男熊嚶肪€，目標是使得汽車廠A的需求得到滿足，并能在一定約束下，如A廠與供應商雙方的時間窗、選配車輛的容載率及利用率等條件，達到以路程最優(yōu)、成本最小等目的.基于A廠產業(yè)需求和物流管理實際情況需要不斷更新最優(yōu)運輸方案，更新過程如圖1所示，汽車廠A高集載率的循環(huán)取送貨物流模式的流程如圖2所示.

圖1 循環(huán)取貨動態(tài)制定最優(yōu)方案示意圖

圖2 汽車廠A循環(huán)取送貨流程圖

2 改進的算法設計

在傳統(tǒng)的智能優(yōu)化算法中，將每一個粒子看作問題的一個解的形式就是粒子群算法.目前該算法已經(jīng)成功應用于多個領域，如云工作流調度、文檔聚類、經(jīng)濟負荷分配、水庫系統(tǒng)運行優(yōu)化問題、移動機器人的定位以及車輛路徑規(guī)劃問題等.相比較而言，粒子群算法的理論概念易理解、參數(shù)設計和改進策略結構鮮明，尤其在解決多維度目標的路徑規(guī)劃問題具有絕對的優(yōu)勢.其內在特點在于可以通過全局更新與個體更新相結合的方式更新粒子的位置.在隨機搜索過程中最核心的環(huán)節(jié)就是如何定義全局和個體，選擇一個到當前迭代完成時的最好粒子個體作為整個粒子群的示例，這個示例就是全局最優(yōu)粒子，它隨著迭代次數(shù)的增加，可能會不斷發(fā)生變化以完成更高質量的搜索.個體最優(yōu)粒子就是當前粒子到當前迭代完成時的最好粒子.隨著粒子群位置的更新，搜索到的解的質量也隨之提高.但粒子的速度和位置都是有范圍限制的，在這里，該范圍是基于Q市智能地圖的汽車廠A與各個供應商之間的位置信息，并將想要超越范圍的路線加以懲罰的方式融入設計當中，避免出現(xiàn)路線超出市區(qū)范圍的問題.

無論是全局更新還是個體更新，粒子的位置必然離不開速度的影響，粒子位置更新公式為

其中：Xk、Xk+1分別表示第k代和第k+1代時粒子i的位置；Vk、Vk+1分別表示第k代和第k+1代時粒子i的速度分別表示第k代個體與全局最優(yōu)粒子的位置；r1和r2設置為0至1之間的隨機數(shù)；c1和c2為常數(shù).

本文提出的新算法在利用粒子群算法求解路徑優(yōu)化問題時，不僅傳承了基本框架、編碼方式簡潔及參數(shù)少的特點，又將多種搜索算法融合在由粒子構成的異質網(wǎng)絡中，并將汽車廠A循環(huán)取貨過程中的反饋加入到動態(tài)調整物流方案當中.進一步在每個粒子更新位置過程中嵌入重新定位操作，在主循環(huán)結束后對全局最優(yōu)粒子再進行大鄰域上和自適應搜索（ALNS）［10］操作.通過帶有隨機性的destroy、repair方法構造新解，基于物流實際反饋動態(tài)評估每種方法，從而對解空間進行啟發(fā)式搜索，直至找到高質量的解.

3 基于粒子群和大規(guī)模自適應鄰域搜索算法的設計

為了驗證本文提出的基于粒子群和大規(guī)模自適應鄰域搜索算法的正確性、適用性與優(yōu)越性，將Solomon數(shù)據(jù)集［11］中包含的rc205算例的隨機23個點（包含一個總體裝配中心）作為測試集算例，分別應用于遺傳算法、應急運輸路徑問題中提出的改進遺傳算法［12］和本文提出的新算法.其中，測試集算例中包含供應商的坐標、總體裝配中心的貨物需求量、供應商的服務時間、每個供應商的時間窗要求、可選配車輛總數(shù)、運輸車輛的最大容載率等多種信息.接下來，將三種算法求解目標函數(shù)的性能作為目標，對三種算法求解目標函數(shù)進行對比分析，分別對三個算法的程序運行10次，將車輛數(shù)、最小成本、最小里程求平均值，結果得出，在使用車輛數(shù)量相同時，新算法的平均最小成本和最小里程均是三者最低.整個試驗過程中，遺傳算法收斂速度較慢，而且基于成本的收斂值也不大理想，大概在360代時收斂到最小值613.551 8元.而應急運輸路徑問題中提出的改進遺傳算法的全局收斂性比前者強，大概在260代時候收斂到最小值419.994 4元.而新提出的算法全局收斂性更強，前期就能迅速收斂至最小值附近，而且相比較而言，收斂值更好，大概120代時收斂到最小值331.802元，其最優(yōu)配送方案路線如表1所示.

表1 最優(yōu)配送方案路線表

4 數(shù)值仿真結果

針對帶有左右時間窗容量受限的循環(huán)取貨車輛路徑優(yōu)化問題，為驗證新提出算法的有效性及優(yōu)化過程中的收斂情況，以Q市地圖為例，選取45個汽車零配件供應商和汽車廠A總體裝配中心實際地址建立坐標系并進行算法仿真，坐標系建立及具體的最優(yōu)配送方案路線如圖3所示.基于Q市實際路況選取坐標原點，將各個配送方案的起始點設為汽車廠A，即配送中心坐標為（100，100），汽車廠A選配車輛分別向各個汽車零部件供應商按需循環(huán)取貨，45個汽車零配件供應商與汽車廠A的相對位置換算成坐標距離，東西方向為橫向距離，即x軸，南北方向為縱向距離，即y軸，單位為百米.例如2號零部件供應商在A廠的西南方向，西向2.1 km，南向3.4 km處；車輛對零部件供應商服務時間包括其進出供應商公司的時間和裝載汽車零部件的時間，設為30 min；假設各個供應商公司汽車零配件包裝箱大小相同，根據(jù)選配車輛的大小不同，普通車輛容載率設為100箱，加長車輛容載率設為150箱；選取A廠總裝中心和所有供應商的左時間窗的最小值，將其設為0，其他時間窗以0為界，以分鐘為單位換算成每個供應商的左右時間窗，例如已選取左時間窗2：30為最小值，3號供應商的服務時間是3：35~4：56，則3號供應商的左時間窗為3：35~2：30=65 min，右時間窗4：56~2：30=146 min.最優(yōu)配送方案路線如表2所示.仿真參數(shù)設置種群初始值隨機，優(yōu)化收斂過程如圖4所示，仿真結果顯示當?shù)螖?shù)為第14代左右時，最優(yōu)值開始呈現(xiàn)收斂狀態(tài).當?shù)螖?shù)為第100代時，全局最優(yōu)解總成本為9 916.651 1元，其車輛使用數(shù)目為18輛，車輛行駛總距離為2 910.718 km，違反受限容量車輛數(shù)目為1輛，違反約束左右時間窗車輛為1輛，算法尋優(yōu)時間為110.678 171 s.

圖3 最優(yōu)配送方案路線圖

圖4 優(yōu)化收斂圖

表2 最優(yōu)配送方案路線

5 結語

本文提出了一種基于新一代信息技術下的粒子群和大規(guī)模自適應鄰域搜索算法，解決了以汽車廠A為實例的汽車零部件運輸最優(yōu)路徑規(guī)劃問題.首先，以實際限制將范圍設定為Q市內，將A廠與各個供應商之間的配送任務關系進行初始化；其次，建立滿足容載率約束和時間窗約束懲罰值的適應度函數(shù)；第三，在粒子群更新過程中，選擇利用大規(guī)模自適應鄰域搜索算法移除和插入供應商，使總運輸距離盡量小.基于相同測試集對三種不同的算法運行結果進行了對比分析，對比結果顯示新提出的算法在性能上具有顯著的優(yōu)越性；最后，以實際運營數(shù)據(jù)為例進行了數(shù)值仿真，求解出汽車零部件的最優(yōu)配送方案和線路圖.數(shù)值仿真結果闡明了新算法的有效性和優(yōu)化過程中的收斂情況.以汽車廠A實際運營需求和動態(tài)反饋作為依據(jù)，新提出算法面對多目標、多車程的汽車零部件循環(huán)取貨的實際問題是一種有效的智能路徑規(guī)劃方法，既能使循環(huán)取貨速度提升、成本費用降低，還可以有效緩解物流車輛造成城市內部的交通壓力.