物流管理-校園外賣配送路徑優(yōu)化研究——以廣東藥科大學為例論文

1、校園外賣配送路徑優(yōu)化研究以廣東藥科大學為例【摘要】近年外賣O2O模式發(fā)展越來越快，針對廣東藥科大學外賣配送效率低、缺少時間窗約束和配送成本存在的問題，如何優(yōu)化配送路徑是一個重要的決策問題，所以本論文進行校園外賣配送路徑的優(yōu)化研究。本文以配送成本最小化為目標，通過觀察法和實地調(diào)查法，構(gòu)建具有軟時間窗約束的模型。采用節(jié)約里程法，對數(shù)據(jù)進行處理，考慮到時間窗，將時間窗加入到節(jié)約里程法中求解模型，得出配送路徑優(yōu)化方案。通過采用節(jié)約里程法，本文對以時間窗為約束的模型進行了有效的求解，優(yōu)化了校園外賣配送路徑，有效地解決了外賣配送存在的問題?！娟P(guān)鍵詞】外賣配送；車輛路徑問題；節(jié)約里程法；時間窗注：本論文（設(shè)

2、計）題目來源于教師的國家級（或省部級、廳級、市級、校級、企業(yè)）科研項目，項目編號為： 。Study on the optimization of distribution route of campus take outTaking Guangdong Pharmaceutical University as an exampleAbstractDelivery O2O model is developing rapidly in recent years.How to optimize the distribution route is an important decision-makin

3、g problem in view of the low efficiency,lack of time window constraints and delivery cost in Guangodng Pharmaceutical University.Therefore this thesis studies the opti- mization of delivery route on campus.In this paper,minimizing the cost of distribution,constructs a model with soft time window con

4、straint through observation method and field investigation method to process the data,takes time window into account,adds time window to solve the model of mileage saving method,and obtains the distribution path optimization scheme.By using the method of saving mileage,this paper effectively solves

5、the model with time window as constraint,optimize the delivery path of campus take-out,and effectively solves the existing problems of take-out delivery.Keywordstake out distribution vehicle routing problem mile saving algorithm time window目 錄1前言11.1研究目的和意義12路徑優(yōu)化國內(nèi)外研究現(xiàn)狀32.1國外研究現(xiàn)狀32.2國內(nèi)研究現(xiàn)狀53.校園外賣配送路

6、徑優(yōu)化研究83.1外賣配送問題分析83.2模型構(gòu)建113.2.1模型建立113.2.2算法理解123.2.3路徑優(yōu)化134.結(jié)論19參考文獻21致謝231前言1.1研究目的和意義隨著互聯(lián)網(wǎng)和信息技術(shù)的發(fā)展、消費者需求的增加和生活節(jié)奏的加快，一種名為O20(Online to Offline)的電子商務(wù)模式出現(xiàn)了，它將線下的消費者與線上互聯(lián)網(wǎng)連接在一起，通過在線支付即滿足了消費者的需求、一定程度上為商家增加了利潤。餐飲行業(yè)利用了這一優(yōu)勢，美團、餓了么等外賣平臺開始發(fā)展，外賣020模式形成，它是商家依托互聯(lián)網(wǎng)，使用信息技術(shù)與線下客戶進行聯(lián)系，以客戶需求為導向，以外賣資源整合為核心，為客戶提供豐富的

7、外賣信息，并由外賣平臺的配送人員為客戶提供上門外賣配送服務(wù)，使客戶不用出門就能享受到外賣配送服務(wù)的經(jīng)營模式。消費者因時間不夠、不想走路等原因?qū)е聼o法及時就食的情況，這一模式在很大的程度上進行了解決，根據(jù)中國產(chǎn)業(yè)信息網(wǎng)，2018年，我國外賣O2O行業(yè)整體規(guī)模約4712億元，比往年增加了1712億元0，所以，外賣平臺發(fā)展得越來越快，外賣配送服務(wù)深受廣大社會群眾的歡迎，包括家庭、校園、工作單位等。而在本文中研究的對象校園外賣，與其他外賣有著不同：（1）配送對象不同，校園外賣的配送對象主要是其校園內(nèi)的客戶，其他外賣的配送對象范圍更廣泛，例如住宅區(qū)、工作單位；（2）配送成本不同，因為校園外賣的配送范圍主

8、要集中在校園，配送范圍相對較小，雇用的配送員也相對較少；（3）配送路徑不同，其他外賣的配送范圍可能是整個城市，配送路徑多而復雜，進行優(yōu)化的難度大，而校園外賣配送路徑的優(yōu)化則相對較簡單。配送成本與配送路徑有關(guān)，本文選擇以廣東藥科大學為對象去研究校園外賣配送路徑的優(yōu)化。廣東藥科大學的外賣行業(yè)從2016年起在逐步發(fā)展，入駐外賣平臺的商家越來越多，它們主要分布在第一、二飯?zhí)?，都由鑫茂餐飲管理有限公司負責，是大學里面主要的配送點。配送點較集中，但是客戶點分布較分散，如宿舍樓和教學樓，他們的數(shù)量多，并且宿舍樓和一些宿舍樓、教學樓之間的距離跨度大，從配送點到取貨點的配送路徑繁瑣，而配送員大部分為大學生，經(jīng)驗

9、少，更換頻率快，他們?nèi)绻荒芗皶r選擇優(yōu)化或最優(yōu)的配送路徑，一天配送的數(shù)量就達不到理想效果，使得配送效率降低，進而造成商家配送物流成本較高、外賣到達客戶手中時間過長、影響客戶體驗等后果。而且因為外賣消費規(guī)模在不斷擴大，也會使商家陸續(xù)招聘外賣配送人員，從而使配送成本提高。所以雖然這三年來大學外賣行業(yè)發(fā)展得不錯，但是為了提高配送員的配送效率、減少配送成本，我們有必要對外賣配送路徑進行優(yōu)化研究，使商家為客戶提供更加完善的外賣配送服務(wù)。在當今社會，研究校園外賣配送路徑優(yōu)化方案具有一定的意義。對客戶來說，它有利于外賣在限定時間內(nèi)盡可能地到達他們手中，保障自身利益；對配送員來說，這有利于他們減少不必要的行走

10、路程，提高外賣配送效率，增加訂單完成量，靈活應(yīng)對客戶取消訂單等突發(fā)情況，以及獲得更高的收入；對商家來說，配送成本是其運營成本的主要組成部分，路徑優(yōu)化有利于減少自身的配送成本，獲得更大的利潤，也有利于贏得更多的客戶，在同行間提升更大的競爭力，對一個商家的發(fā)展起著推動作用，保障外賣市場能夠穩(wěn)健發(fā)展。校園外賣配送路徑優(yōu)化研究具有一定的應(yīng)用價值。本論文要研究的是以配送成本最小化為目標，以時間窗為約束條件，從第一飯?zhí)玫礁鱾€宿舍、教學樓之間的配送路徑優(yōu)化問題，對大學外賣配送的實際情況進行數(shù)據(jù)的收集，按照實際構(gòu)建模型，使用合適的算法求解，能夠根據(jù)實際運行進行調(diào)整，并得出具體的方案，不僅可以改進廣東藥科大學自

11、身外賣配送存在的問題，還可以為其他模式的路徑優(yōu)化研究提供輔助和參考。242路徑優(yōu)化國內(nèi)外研究現(xiàn)狀2.1國外研究現(xiàn)狀配送路徑的優(yōu)化，是一個車輛路徑問題，即VRP問題。在國外，對于車輛路徑問題和路徑優(yōu)化的研究較多，而且起步較早，1959年，Dantzig和Ramser首次提出車輛路徑問題0，VRP問題可描述為：有一個起點和若干個客戶點，已知各點的地理位置和需求，如何規(guī)劃一條最優(yōu)的路徑，使得每個客戶點的需求預測得到滿足，并能在一定的約束條件下，達到路程最短、成本最小、耗費時間最少等目的。而VRP問題屬于NP（non-deterministic polynomial）hard問題，求解難度大。在實際應(yīng)

12、用中，根據(jù)不同的情況，它可以分為多個不同類型的問題，如帶多個時間窗VRP、同時取送貨VRP、動態(tài)VRP等，情況越多，約束越大，求解的難度越大。隨著對車輛路徑問題越來越深入的了解，精確式算法和啟發(fā)式算法逐漸出現(xiàn)。1962年，Balinski提出VRP的集分割法0，在確定可行解集合基礎(chǔ)上對其分割并進行優(yōu)化，建立了最簡單的VRP模型，它的不足在于當VRP問題沒有嚴格約束下，不能準確選擇可行解的取值范圍，計算空間大，是適用于約束少的精確式算法；20世紀60年代初，Land Doig和Dakin提出了分支定界法，成功求解了含有65個城市的旅行商問題，其基本思想是根據(jù)某種策略將原問題的可行域分解為越來越小

13、的子域，并檢查某個子域內(nèi)整數(shù)解的情況，直到找到最優(yōu)的整數(shù)解或證明整數(shù)解不存在，是求解整數(shù)規(guī)劃最常用的方法，因此它的計算時間長，適合小規(guī)模的車輛路徑問題。2007年，Stefan Ropke和Gilbert Laporte等人對帶有時間窗的取件和送達問題運用新的分支剪切法進行求解，時間窗是指允許車輛通過的時間段，他們分析了時間窗限制了車輛可能會到達各個取貨點和送貨點的時間，為VRPTW生成了優(yōu)先級不等式、容量不等式和不可行的路徑不等式， 通過實例證明，這些新公式可以解決大規(guī)模的VRPTW，最大包括194個節(jié)點0；20世紀50年代初美國數(shù)學家Bellman R E在研究多階段決策過程的優(yōu)化問題時，

14、把多階段過程轉(zhuǎn)化為一系列單階段問題，提出了優(yōu)化問題的新方法動態(tài)規(guī)劃，他在最短路線、庫存管理、資源分配等方面得到了廣泛的應(yīng)用。Clarke G和Wright J W在1964年提出了節(jié)約法0，指配送中心與各個客戶點形成多條配送路徑，針對任意兩條配送路徑的節(jié)約值，最后對路徑進行合并，目的是從多條配送路線中選擇最佳路徑，使配送時間最短和配送成本最低，它適合運用于小規(guī)模的VRP問題，是較快和容易實現(xiàn)求解的啟發(fā)式算法。之后，M.Shigeno研究了在不允許減少給定的弧流的前提下，對于如何有效地運用網(wǎng)絡(luò)，做出了多目標規(guī)劃有效集的優(yōu)化，提出了算法。1975年由Holland J H教授提出了著名的遺傳算法，

15、遺傳算法是一種基于“適者生存”的高度并行、隨機和自適應(yīng)的算法,通過復制、交叉、變異將問題解編碼表示的一代代“染色體”群不斷進化,最終收斂到最適應(yīng)的群體,從而得到問題的最優(yōu)解，是解決搜索問題的算法，由于遺傳算法處理由參數(shù)集編碼構(gòu)成的染色體個體，參數(shù)約束對算法的影響不大，適用于處理難以解決的非線性問題，所以它在車輛路徑問題方面的應(yīng)用較廣泛。禁忌搜索算法（Tabu Search）是一種亞啟發(fā)式隨機搜索算法，于1986年由美國科羅拉多大學科學家Fred Glover提出，目的是尋找全部區(qū)域的最優(yōu)解，避免迂回搜索，實現(xiàn)全局優(yōu)化，是局部鄰域搜索的一種擴展，也是人工智能的體現(xiàn)，對組合優(yōu)化問題VRP問題的解決

16、有著很大的作用，后來，又出現(xiàn)了蟻群算法，于1992年由Marco Dorigo教授等人提出，他們發(fā)現(xiàn)蟻群可以在不同的環(huán)境，尋找最短的路徑去發(fā)現(xiàn)食物，這樣的行為使他們提出并運用蟻群算法去對車輛路徑問題進行優(yōu)化，并成功進行求解，它是一種概率型算法，具有啟發(fā)式搜尋、信息反饋、分布計算的特點，同時也是全局優(yōu)化的啟發(fā)式算法，對旅行商問題、指派問題等問題都有實際的應(yīng)用價值。隨著時代的變化，越來越多人對啟發(fā)式算法進行改進并運用，Aghezzaf E H等人對單配送循環(huán)庫存路徑問題進行研究，將它轉(zhuǎn)變?yōu)橥购瘮?shù)優(yōu)化問題，針對凸函數(shù)的性質(zhì)求出最優(yōu)解，對路徑優(yōu)化問題進行了深一步的研究0。一般來講，精確式算法因為引入嚴

17、格的數(shù)學方法，計算量會隨著問題規(guī)模的增大呈指數(shù)增長，因此容易發(fā)生指數(shù)爆炸問題，使得它只能求解小規(guī)模的確定性VRP問題，而啟發(fā)式算法用于求出組合優(yōu)化問題的可行解，不追求最優(yōu)解，比精確式算法具有靈活性，由此看來，相比精確式算法，啟發(fā)式算法的應(yīng)用更為廣泛。2.2國內(nèi)研究現(xiàn)狀相比在國外，國內(nèi)對路徑優(yōu)化問題的研究較遲，國外研究文獻為國內(nèi)研究打下了基礎(chǔ)，它的源頭可追溯到1999年，姜大立先生等人使用遺傳算法對車輛路徑進行優(yōu)化0，構(gòu)造了VRP問題的染色體表達，并對染色體進行了可視化映射，而實驗結(jié)果證明遺傳算法優(yōu)于較為簡單的節(jié)約法，而且它能較快地求出問題的優(yōu)化解，是普遍運用的啟發(fā)式算法。鄭靜等人在時間約束條件

18、下使用節(jié)約里程法對配送路徑進行優(yōu)化，考慮了配送距離和時間窗兩項因素，在保證時間允許的同時降低了物流配送成本，這是在原來降低配送成本的基礎(chǔ)上增加了時間窗的約束條件，使研究更加深入Error! Reference source not found.。2007年，李兵先生等人基于客戶動態(tài)需求的約束條件將動態(tài)車輛路徑問題轉(zhuǎn)變?yōu)殪o態(tài)車輛路徑問題，靈活運用適用于靜態(tài)車輛路徑問題的算法進行求解，并得到路徑優(yōu)化的結(jié)果0。2016年，吳文佳對節(jié)約里程法進行改進，將時間轉(zhuǎn)變?yōu)榫嚯x，加入當量距離，并應(yīng)用于節(jié)約里程法，證明了節(jié)約里程法即使在加入約束條件后，仍可以順利進行研究和運用0。李昌旺先生在較早時期對外賣配送路徑

19、也有著一定的研究0，他分析了影響配送路徑的因素，根據(jù)配送路徑優(yōu)化原則，采用單回路運輸TSP模型對線路進行優(yōu)化，之后利用交換的方法求路徑的最優(yōu)解，這個研究使用的模型較簡單，更適用于送貨點少的配送路徑優(yōu)化。許多學者仍對啟發(fā)式算法不斷地進行改進。邰曉紅和李璐通過改進節(jié)約法解決單車場非滿載和具有時間窗約束的車輛路徑問題0，相比傳統(tǒng)的節(jié)約法，它可以解決更多的實際問題，為以后路徑優(yōu)化問題解決提供一定的文獻基礎(chǔ)，也給予了本次論文研究更多的思路。范厚明等人針對客戶點需求模糊和具有時間窗約束的車輛路徑問題0，設(shè)計并運用了自適應(yīng)大規(guī)模鄰域搜索算法（ALNS），并證明了它搜索性能好、有效，是解決與客戶模糊需求和時間

20、窗約束相關(guān)的VRP問題的算法，所以，解決VRP問題不僅僅局限于現(xiàn)有的、固定的算法，靈活地去發(fā)現(xiàn)、設(shè)計和解決是非常有用和重要的能力。對于外賣配送路徑優(yōu)化的研究數(shù)量不多。2016年，陳萍和李航針對外賣配送路徑優(yōu)化問題，以客戶滿意度最大化為目標，建立O2O外賣配送的混合整數(shù)規(guī)劃模型，并使用改進遺傳算法進行求解，最后得出了適當提高服務(wù)時間窗的彈性，可以有效地提高客戶滿意度的結(jié)論0，作者在研究中充分考慮了外賣配送路徑優(yōu)化問題的約束條件，構(gòu)建了模型，有利于整個路徑優(yōu)化問題的求解。李桃迎（2016）也研究了外賣配送的路徑優(yōu)化0，他們不將時間窗作為約束條件，而是用時間懲罰成本去衡量外賣配送超出時間窗的情況，將

21、其作為變動成本改變目標函數(shù)，再使用基于K-means聚類分析的遺傳算法進行求解，降低了算法求解難度。佟瑞在基于眾包模式的基礎(chǔ)上對外賣配送路徑進行優(yōu)化0，使用改進的遺傳算法和蟻群算法進行了眾包搶單、派單模式上的配送路徑優(yōu)化，得出了配送速度在一定數(shù)值后不會對配送結(jié)果產(chǎn)生很大的影響，載貨量對配送結(jié)果無影響的結(jié)論，是一次大規(guī)模的路徑優(yōu)化實驗，對以后的路徑優(yōu)化研究有很大的幫助。隨著時代的發(fā)展和技術(shù)的進步，對于路徑優(yōu)化和車輛路徑問題的研究越來越多，也越來越深入。龐燕，羅華麗等人對車輛路徑問題進行總的概括，包括定義、種類、求解方法等，為人們進行研究提供了良好的基礎(chǔ)0。國外研究對各種路徑優(yōu)化的求解進行了初步的

22、定義和概括，各方面有待改進，國內(nèi)關(guān)于算法的大部分研究則是算法的引用和改進，缺少創(chuàng)新；在外賣配送路徑優(yōu)化方面，因為國內(nèi)外賣行業(yè)的持續(xù)發(fā)展，所以國內(nèi)研究比國外研究得更深入。但是在國內(nèi)外研究文獻基礎(chǔ)上，遇到時間窗、動態(tài)變化等約束條件，人們已經(jīng)可以運用各種算法和改進的算法對相關(guān)路徑優(yōu)化問題進行求解，也得到了不錯的結(jié)論，這也為以后的研究奠定了基礎(chǔ)，但無論是精確式算法、啟發(fā)式算法或是其他改進的算法，計算量和難度都非常大，現(xiàn)在的文獻研究還沒有真正將VRP問題求解地更簡單、更方便。車輛路徑問題的求解難度大，伴隨社會的發(fā)展，會遇到約束條件越多或建模越難的路徑優(yōu)化問題，相信以我們的力量，會更容易地解決它們。到目前

23、為止，雖然對于外賣配送路徑的研究仍舊缺乏，但是外賣行業(yè)仍在持續(xù)發(fā)展，外賣配送路徑優(yōu)化的問題不容小覷，經(jīng)濟基礎(chǔ)決定上層建筑，有“硬件”也會有“軟件”，在外賣發(fā)展的同時，也會有各種關(guān)于外賣配送的研究分析和解決問題，所以，未來對于車輛路徑問題研究會越來越深入和成熟。在本文中，筆者使用節(jié)約里程法對廣東藥科大學中山校區(qū)的外賣配送路徑進行優(yōu)化。原因有：（1）因為節(jié)約里程法適用于顧客需求穩(wěn)定的配送中心，而廣東藥科大學的配送中心主要是第一飯?zhí)?，顧客大部分在宿舍樓或教學樓分布，客戶需求一般為1到2份外賣，需求較穩(wěn)定；（2）這個方法要求各配送路線的負荷要盡量均衡，而廣藥的配送員主要使用外賣籃子裝外賣，限定裝載量；

24、（3）它針對求解的配送規(guī)模不大，適用于校園外賣配送路徑優(yōu)化的求解；（4）而且節(jié)約里程法需要預測需求的變化及發(fā)展趨勢，商家可根據(jù)外賣平臺上客戶的需求、評分等，預測廣藥顧客的需求變化；（5）相較于其他算法，節(jié)約里程法的計算過程和步驟使人更易理解，容易操作，筆者有關(guān)于節(jié)約法的理論體系基礎(chǔ)，不必花其余時間研究其他算法。所以節(jié)約里程法對筆者來說適用于配送路徑的優(yōu)化研究。3.校園外賣配送路徑優(yōu)化研究3.1外賣配送問題分析本論文研究的是廣東藥科大學中山校區(qū)的外賣配送路徑優(yōu)化問題。與其他同城的學校相比，筆者是廣東藥科大學的學生，有著地理位置的先機和人脈資源的優(yōu)勢，更有利于進行準備工作、收集數(shù)據(jù)、實地觀察、咨詢

25、和改進問題，例如觀察有些外賣配送員外賣的裝載量大約是多少；向商家們咨詢他們的配送成本如何計算；還可以記錄客戶點與配送中心間的實際距離等。而且廣東藥科大學中山校區(qū)的飲食管理嚴格到位；運營設(shè)備齊全；入駐外賣商家多；外賣品種豐富多樣；經(jīng)常有各種優(yōu)惠活動吸引消費者，客戶的需求量大；出現(xiàn)問題也有針對的對象，這些都有利于調(diào)研數(shù)據(jù)的收集和增加配送路徑優(yōu)化的真實性，研究其配送路徑的優(yōu)化有一定的意義，所以選擇它作為研究對象去進行分析。經(jīng)典VRP問題僅以配送車輛總行駛距離最短或配送路線最少為目標，但是根據(jù)現(xiàn)實情況，由于交通堵塞、客戶需要等待的時間等因素，以此為目標反而會延遲送貨的時間，降低客戶的滿意度0。所以本文

26、以滿足客戶時間窗要求和配送成本最小化為外賣配送路徑優(yōu)化的目標。圖3-1是廣東藥科大學外賣配送示意圖。由圖中所示，配送員從配送中心出發(fā)，一般根據(jù)就近原則先到A點或B點，然后再到附近的配送點進行配送，所以有可能是A C E F D B 4 3 2 1的配送路徑，也有可能是A C E F 4 3 2 1 D B的配送路徑，但是根據(jù)廣東藥科大學的實際情況，首先每棟宿舍都有7層，每棟教學樓都有6層，每層可能都有客戶訂單，而各自的訂單時間不一，如果配送員只按照就近原則配送，就是忽略了客戶的時間要求，降低了客戶對這次外賣配送的好感，那么以上都不一定是最優(yōu)路徑；其次宿舍樓之間、和教學樓之間的距離近有20m，遠

27、達有700m，配送任務(wù)不僅僅只有一個人去完成，這樣反而增加了成本，有時候需要合理分配配送員去減少成本，優(yōu)化路徑就會增加到2-3條甚至更多。所以圖中A、B、C、D、E、F點都屬于字母棟，1、2、3、4點則屬于數(shù)字棟，字母棟之間，數(shù)字棟之間的距離相差不大，它們各自可以形成一條配送路徑，而從哪個點出發(fā)，哪個點結(jié)束是由實際因素，如時間限制、突發(fā)情況等決定的，圖中是多種情況的一種結(jié)果，也是較簡潔清晰的配送路徑。廣東藥科大學外賣配送路徑具體優(yōu)化可以根據(jù)其存在的問題進行相應(yīng)地求解。圖3-1 校園外賣配送示意圖根據(jù)觀察法，對第一飯?zhí)门渌椭行?、商家和配送員進行觀察，該校園在外賣配送方面存在以下問題：首先，配送效

28、率低。由于配送員絕大多數(shù)是兼職的大學生，大一、大二生居多，配送經(jīng)驗不足，起始完成配送的外賣訂單數(shù)量肯定不足；他們可能分別以走路、騎自行車、開電動車的配送方式進行配送，對如何分配配送路徑不熟悉，造成效率差異大；大學生需要上課，大部分工作的時間在下課或放假后的時間，工作時間不穩(wěn)定，而且他們在職的時間不長久，積累經(jīng)驗的時間少，導致配送效率低。其次，配送成本升高。第一飯?zhí)玫拿總€商家都是獨立的個體，他們也會進行合作，通過一個或多個配送員對他們的外賣訂單進行共同配送，這有利于降低商家們的配送成本，但是因為配送員的配送效率不高，配送工具使用的次數(shù)多，籃子的裝載量等于車輛的裝載量，使得單位外賣的配送成本增加，

29、而配送員的更新頻率高，每個配送員的工資大約平均為100元/天，增加了商家的雇傭成本；配送員在整個校園進行外賣配送的路徑是復雜的，路程遠的外賣配送，可能會產(chǎn)生相應(yīng)的成本。第三，客戶滿意度不高。民以食為天，客戶對校園外賣配送的滿意度，很大程度取決于外賣送達到他們的時間?，F(xiàn)在的外賣軟件，都會提供給客戶配送時間的選擇，雖然校園內(nèi)學生們對配送時間的要求不是特別高，但是如果過于超過客戶期望的配送時間，也就是客戶要求的時間窗范圍，就會使客戶的滿意度逐漸降低，最后為0。廣東藥科大學的消費者對外賣配送的滿意程度低體現(xiàn)在給予商家差評、投訴商家、拒絕購買該商家的外賣等，這都會造成商家的形象和名譽受損，影響其發(fā)展。而

30、這是外賣配送普遍存在的問題，也是主要問題，路徑優(yōu)化需要時間窗的約束，再進行配送。第四，缺少時間窗的約束，配送員的配送任務(wù)受客戶配送時間要求、客戶位置、自身所在位置、外賣裝載量、配送成本和客戶的動態(tài)需求影響，但是因為配送員經(jīng)驗少，總會依賴就近原則和僥幸心理，容易忽略客戶要求的配送時間，缺少時間窗的約束，從而降低了客戶的滿意度。因為時間窗的約束，所以配送員需要選擇優(yōu)化后的路徑去配送。時間窗是指物流活動過程中，如送貨、配貨、收貨，供應(yīng)鏈企業(yè)之間或企業(yè)內(nèi)部上下游工序之間，指定專門的車輛、企業(yè)、產(chǎn)品等，完成特定作業(yè)任務(wù)的物流服務(wù)時間范圍0。它又分為硬時間窗和軟時間窗，硬時間窗要求配送車輛必須在時間窗內(nèi)到

31、達，否則服務(wù)會被拒絕，產(chǎn)生較大的懲罰成本；軟時間窗對配送車輛的約束比硬時間窗小，配送車輛盡可能地在時間窗內(nèi)將貨物送達客戶手中，否則會產(chǎn)生一定的懲罰成本。以下為硬時間窗和軟時間窗的示意圖，T表示時間，C表示懲罰成本，a和b則代表某時間窗的范圍，如果超出時間窗a,b的范圍，硬時間窗的懲罰成本是固定的最大值，軟時間窗的懲罰成本會逐漸增加。 圖3-2硬時間窗示意圖 圖3-3軟時間窗示意圖根據(jù)廣東藥科大學外賣配送的實際情況，一般情況下，配送員提前將外賣送達到客戶手中，即在a之前完成配送任務(wù)，并不會產(chǎn)生任何懲罰成本，所以本文不考慮提前完成外賣配送的影響。配送員在時間窗范圍外將外賣配送到達到客戶手中產(chǎn)生的影

32、響有很多，大部分客戶在一般情況下不會選擇拒收，說明當配送時間超出時間窗范圍時，還有一段客戶的額外等待時間，而這段時間產(chǎn)生的懲罰成本會逐漸增加，當達到一個點時，懲罰成本上升到一個值，這時客戶的等待時間已超出了額外等待時間，客戶會拒收或取消外賣、對商家反饋差評等，產(chǎn)生了較大的懲罰成本，因此這是一個軟時間窗約束的配送路徑優(yōu)化問題。3.2模型構(gòu)建3.2.1模型建立按照上述校園外賣配送存在的問題，建立相關(guān)變量。設(shè)有一個配送中心，為P0；第i個客戶點為Pi（i=1，2，3，n）；第i個客戶點的需求量為gi；第k輛車為hk（k=1，2，3，K），每輛車配送的外賣重量不能超過車輛的裝載量，qk表示車輛k的最大

33、裝載量；由配送中心P0向n個客戶點進行配送，P0到客戶點Pi的距離為d0i，客戶點Pi到客戶點Pj的距離為dij，配送員配送結(jié)束后回到配送中心；每單位路程距離的配送成本為a。因為有軟時間窗的約束，配送車輛到達客戶點Pi的時間為Bi；允許配送車輛到達客戶點Pi的最早時間為Ai；允許配送車輛到達客戶點Pi的最晚時間為Ci，這三者之間的關(guān)系為AiBiCi；從客戶點Pi到達客戶點Pj的時間為Eij；Fi表示配送員到客戶位置的時間，不包括卸貨時間；Di表示配送員在i點裝貨（卸貨）時間；xijk表示車輛k從客戶點i去到客戶點j，事件發(fā)生時取1，否則取0。構(gòu)建該模型需要的約束條件為：（1）每條配送路線的外賣

34、總重量不能超過車輛的最大裝載量；（2）配送車輛到達客戶點的時間滿足客戶的要求；（3）每個客戶只能被一輛配送車輛或一個配送員完成配送；（4）配送車輛從配送中心P0出發(fā)，完成所有客戶的配送任務(wù)后回到配送中心。下面建立以配送成本最小為目標函數(shù)，軟時間窗為約束的路徑優(yōu)化模型： minz=i=0nj=0nk=1Kadijxijk （1） st i=0nxijk=yik i,j=1,2,3n; k （2） j=0nxijk=yjk i,j=1,2,3n; k （3） i=0ngiyikqk i=1,2,3.n;k （4） k=1Kyik=1 i=1,2,3n （5） BiCi i=1,2,3n （6）Bi

35、=Fi+Di （7）上述模型中，（1）表示該模型的目標函數(shù)，由配送成本adijxijk形成；（2）表示由車輛k完成客戶點Pi的配送任務(wù)；（3）表示由車輛k完成客戶點Pj的配送任務(wù)；（4）表示客戶點Pi的配送重量不能超過車輛k的最大裝載量；（5）表示客戶點Pi的外賣配送只能由一輛配送車輛完成；（6）表示客戶點i的配送任務(wù)要在時間Ci之前完成；（7）表示配送到達客戶點i的時間。3.2.2算法理解在本文中，使用節(jié)約法求解上述模型。節(jié)約法的原理是設(shè)配送點為P0，客戶點為P1、P2、P3Pn，車輛用k表示，已知任意兩個點Pi和Pj之間的最短距離為dij（i，j=1，2，3，n），有兩種運輸方案:如圖所示

36、，一是派ki和kj兩輛車分別往Pi和Pj送貨；二是將Pi和Pj兩個客戶點的貨物裝在同一輛車ki上，第一種運輸方案的路程為2（di0+dj0），而第二種運輸方案的路程為di0+dj0+dij，按照三角原理，第二種運輸方案比第一種運輸方案行駛的路程要短，節(jié)約度為cij=d0i+d0j-dij（cij0，i，j=1,2,3,n，且ij）。圖3-4 第一種運輸方案示意圖 圖3-5第二種運輸方案示意圖節(jié)約法的求解步驟：（1） 輸入配送中心與客戶點、客戶點之間的距離，算出節(jié)約里程Pi-Pj。（2） 對節(jié)約里程Pi-Pj按從大到小的順序進行排列，將客戶點i和客戶點j連接在一起，如果Pi-Pj的值=0，則這兩

37、點不能連接在一起。（3） 計算客戶點i和客戶點j的總需求量gij，如果gijqk，則連接客戶點i和客戶點j成為一條配送路徑，否則不能作為線路上的點，重新計算。（4） 把時間窗加入路徑中，符合約束條件則形成配送路徑，否則重新計算。（5）總結(jié)路線方案。3.2.3路徑優(yōu)化本文以廣東藥科大學為例，以第一飯?zhí)脼榕渌椭行腜0，從18棟數(shù)字棟宿舍、8棟字母棟宿舍和6棟教學樓中隨機抽取了10個客戶點作為樣本，通過地圖大約計算各個客戶點與配送中心的距離。根據(jù)實地調(diào)查和觀察，商家做好前期準備工作后，在早上11：00后開始進行配送，一般的外賣籃子和外賣箱可以裝10件至15件外賣，配送中心有最大裝載量為10件和15件

38、的配送車輛，按照配送員到每個客戶點的時間以及距離進行計算，估計配送員的平均送貨速度為0.5km/h，單位路程距離的配送成本為12.5元/km，針對上述存在的配送效率低、配送成本高、超出時間窗范圍等問題，通過節(jié)約法去求解模型，以得出外賣配送路徑的優(yōu)化方案。圖3-6是配送中心與各客戶點的距離以及客戶需求的示意圖。圖3-6配送中心與客戶點距離以及客戶需求圖節(jié)約里程法的計算首先需要記錄配送中心與客戶點以及各客戶點間的距離，如表3-1所示。表3-1 配送中心與各客戶點及各客戶點間的距離（單位：km）P010.07120.11 0.03230.34 0.41 0.44340.14 0.07 0.04 0.

39、48450.09 0.01 0.02 0.42 0.06560.51 0.59 0.62 0.15 0.65 0.6670.39 0.37 0.34 0.63 0.28 0.36 0.8 780.46 0.39 0.36 0.32 0.31 0.38 0.48 0.4489 0.31 0.23 0.2 0.54 0.15 0.22 0.71 0.21 0.239100.19 0.11 0.08 0.53 0.03 0.1 0.7 0.32 0.280.12 10 各個客戶點都隨機地包括了字母棟宿舍、數(shù)字棟宿舍和教學樓。配送中心離字母棟宿舍的距離較近，如1、2、4、5、10點，而離教學樓3、6點

40、和數(shù)字棟宿舍7、8、9點的距離都較遠。距離是節(jié)約里程法計算的重要數(shù)據(jù)之一，在一定范圍內(nèi)把握各個點間的距離，能夠有效支撐起節(jié)約里程法的計算。另外，還有需求量等也是需要使用的數(shù)據(jù)，如表3-2。表3-2 客戶點的需求量和時間窗約束客戶點需求量（件）卸貨時間（h） （Ai，Ci160.04（11：00，11：40240.02（11：15，12：30380.06（11：20， 12：50 440.02（11：00，12：00530.01（11：25，11：50670.08（11：30，12：30720.01（11：00，11：15820.01（10：50，11：59100.12（11：00，11：301

41、030.04（11：35，13：00計算個客戶點之間的節(jié)約里程，對節(jié)約里程值為0的數(shù)據(jù)進行去除，將節(jié)約里程按大小順序進行排列，這是節(jié)約里程法的重要步驟之一。表3-3客戶點間的節(jié)約里程（單位：km）120.152300.01340.140.210450.150.180.010.17560.0100.700670.090.160.10.250.120.1780.140.210.480.290.170.490.41890.150.220.110.30.180.110.490.549100.150.2200.30.1800.260.370.3810接下來對節(jié)約里程按大小順序進行排列。表3-4節(jié)約里程排

42、序（單位：km）編號連接點節(jié)約里程編號連接點節(jié)約里程13-60.7205-100.1828-90.54214-50.1736-80.49225-80.1747-90.49232-70.1653-80.48241-20.1567-80.41251-50.1579-100.38261-90.1588-100.37271-100.1594-90.3281-40.14104-100.3291-80.14114-80.29305-70.12127-100.26313-90.11134-70.25326-90.11142-90.22333-70.1152-100.22346-70.1162-40.2135

43、1-70.09172-80.21361-60.01182-50.18372-30.01195-90.18383-50.01 如圖3-7所示，經(jīng)過上述節(jié)約法的步驟，最終得出結(jié)果為4條配送路徑，分別為P0 P3 P6 P0,P0 P7 P9 P8 P0,P0 P4 P10 P2 P5 P0 ,P0 P1 P0。配送距離為2.79km，需要1輛10件配送車輛，3輛15件配送車輛，配送員在配送時經(jīng)常依據(jù)就近原則，配送外賣所需要的路徑減短，安排配送員的數(shù)量減少，使用電動車或自行車的數(shù)量減少，配送成本為 34.875元，配送時間分別為2.16h，2.72h，0.81h，0.32h。但是這忽略了需要到達各客

44、戶的時間，沒有達到客戶的要求，導致外賣送達超時，例如，第三條配送路徑，整條路經(jīng)是基于配送距離安排的，配送員11：00從配送中心出發(fā)時，路徑最短，但是客戶點5要求送達的最晚時間是11：50，而這是配送路徑的最后一個配送點，根據(jù)到達時間和卸貨時間計算，配送到達所需時間是1.14h，到達時是12：14，超過這位客戶要求的時間窗，客戶的滿意度下降。 圖3-7節(jié)約法配送路徑分配圖所以，在配送成本合理時，不超過外賣箱裝載量最大時，也要考慮客戶的時間窗需求，根據(jù)上述節(jié)約法，加入時間窗的約束，建立新的優(yōu)化路徑。根據(jù)各條路徑的時間計算，目前只有第三條路徑需要進行深入優(yōu)化，我們先對一條路徑的配送點進行改進，以免影

45、響到其他路徑的優(yōu)化。第一，因為節(jié)約點最大的節(jié)約里程已經(jīng)不能代表路徑優(yōu)化的唯一依據(jù)，所以我們根據(jù)表3-4，對關(guān)于第三條路經(jīng)節(jié)約點的節(jié)約里程進行重新篩選和排列。整條路經(jīng)是P0 P4 P10 P2 P5 P0 ，配送距離=0.14+0.03+0.08+0.02+0.09=0.36km，因為客戶點5的時間需求得不到滿足，需要這個點進行重新排列，但不能使整條路經(jīng)的配送成本過大，所以先將P5作為第一個配送目標。第二，按照先前的路徑，不改變剩余三個客戶點的配送位置，P5在第一個配送位置，然后測出各客戶點是否符合時間窗的要求、計算總的配送距離和配送成本是否過大，如果都符合要求，則是最終優(yōu)化路徑，否則在第三步繼

46、續(xù)計算。得出這條路徑為P0 P5 P4 P2 P10 P0，配送距離=0.09+0.06+0.04+0.08+0.19=0.46km，比之前增加了0.1km，所需時間為1.01h，滿足了各客戶的時間需求，但是配送成本增加，因為可以進行更靈活的改變，所以繼續(xù)進行優(yōu)化。第三，按照時間窗從早到晚對客戶點進行重新排列，再比較配送距離和配送成本是否差距過大。配送路徑為P0 P5 P10 P2 P4 P0，配送距離=0.09+0.1+0.08+0.04+0.14=0.45km，比第一次增加了0.09km，但是比第二次減少了0.01km，所需時間為0.99h，也比第二次縮短了0.02h，綜合計算，這是第三條

47、外賣配送路徑優(yōu)化最終解。根據(jù)上述，如圖3-8所示，最終外賣配送路徑為P0 P3 P6 P0,P0 P7 P9 P8 P0,P0 P5 P10 P2 P4 P0 ,P0 P1 P0。配送距離為2.88km，需要一輛10件配送車輛、3輛15件配送車輛，配送時間分別為2.16h，2.72h，0.99h，0.32h，配送成本為36元，比第一次的配送成本增加了1.125元，但是這是基于滿足所有客戶時間窗的最小配送成本。運用節(jié)約里程法，相比圖3-7的路徑分布不能全部滿足客戶時間窗的要求，圖3-8的路徑優(yōu)化分布滿足了各客戶點關(guān)于時間窗的需求。圖3-8路徑優(yōu)化示意圖除了節(jié)約法的優(yōu)化外，還可以采取以下措施輔助解

48、決外賣配送路徑存在的問題：第一，對配送員進行培訓。因為配送員大部分為學生，身體素質(zhì)好，在節(jié)約法優(yōu)化的基礎(chǔ)上，配送員根據(jù)優(yōu)化結(jié)果進行配送，配送效率將提高；在時間窗的約束下，配送員對時間更為敏感，同時，這也需要他們有更加好的身體素質(zhì)，去支持他們更好地完成配送任務(wù)。第二，減少配送工具的使用，因為配送中心離客戶點的距離參差不一，在距離短并且訂單量少的情況下，可以選擇步行的方式；減少電動車的使用，將配送工具換為共享單車，也可以有效降低配送成本。 第三，贈送物品提高客戶滿意度。有時候商家的外賣配送非常忙碌，即使對路徑優(yōu)化過，可能也會發(fā)生外賣配送超時的情況，所以可以適當采取贈送食品或物品的方式，維護商家形象

49、，提高客戶滿意度。第四，添加注釋。根據(jù)調(diào)查，有些商家外賣包裝上會直接別上訂單條子，有些則沒有，另外，有些訂單條子上沒有標明客戶要求外賣配送到達的時間。這些都容易使有些外賣配送員忽略關(guān)于客戶時間上的需求，所以商家們盡可能地在訂單條子加上時間，或者在外賣包裝袋子上寫明清楚，提醒配送員注意時間。第五，在客戶點樓下放置儲物柜。配送員可以將外賣放到儲物柜里，及時通知客戶下來拿走，減少了配送員上樓的時間，有利于他們更快地完成配送任務(wù)，而且受2020年疫情影響，人們應(yīng)該更加注意個人的安全問題，這也有利于減少客戶與配送員的直接觸碰，形成一種無接觸配送模式。4.結(jié)論與展望本次對校園外賣配送路徑優(yōu)化的研究，針對外

50、賣配送存在的配送效率不高、達不到客戶時間窗要求等問題和相關(guān)文獻建立了模型，并采取了節(jié)約里程法這個關(guān)于路徑優(yōu)化的啟發(fā)式算法，和加入了時間窗的約束，對其進行一個求解，通過以廣東藥科大學為例，用相關(guān)數(shù)據(jù)證明了在時間窗的約束下，節(jié)約里程法能夠解決校園內(nèi)實際存在的外賣配送問題，能夠有效地研究出路徑的優(yōu)化方案，相信對校園外賣配送路徑優(yōu)化具有一定的應(yīng)用價值，校園外賣配送路徑會得到優(yōu)化，配送服務(wù)也會提高。但是在本次研究中，還存在很多不足：（1）客戶點的定位較廣泛，主要定位在一棟樓和一棟樓之間的距離，在它們之間進行外賣配送，忽略了每層樓之間的外賣配送；（2）車輛路徑問題本身是一個NP-hard問題，與本身的問題

51、環(huán)境、約束條件、目標相關(guān)，求解難度大，時間窗的約束本身也是一個復雜多變的東西，所以本次研究的結(jié)論缺乏精確性；（3）因為時間窗的約束條件構(gòu)成復雜，對整個算法的計算有著很大的關(guān)系，需要更加靈活地進行計算，這次研究中的計算技巧不夠靈活；（4）配送成本問題的解決存在局限性，雖然在本次研究中，配送成本已經(jīng)降低，但是在加入時間窗的約束條件后，因為以客戶時間需求為主，有可能導致配送成本升高或降低；（5）節(jié)約里程法對車輛路徑問題的研究有著很大的作用，可以解決大規(guī)模和小規(guī)模的VRP問題，但是它研究出來的路徑優(yōu)化方案不一定是最優(yōu)的，不確定性強；（6）校園外賣配送路徑的優(yōu)化與其他快遞、超市等配送貨物的配送路徑優(yōu)化不同，它的配送中心相對單一、配送地點相對密集，時間窗的約束屬于軟時間窗，沒有過于嚴謹，