基于遺傳算法的Y物流公司配送路徑優化研究目錄TOC\o"1-2"\h\u98351研究的背景 2202262研究的意義 228089（1）降低物流公司配送成本 310324（2）提高客戶的滿意度 321422（3）提高車輛裝載率 38651（4）提高社會效益 3250623Y物流公司車輛路徑現狀及問題分析 444633.1Y物流公司簡介 496553.2Y物流公司車輛配送路徑運行現狀 6268543.3Y物流公司車輛路徑存在的問題及原因 995193.4本章小結 1233314Y物流公司車輛路徑優化模型構建 12135474.1Y物流公司車輛路徑優化建模 12160573.車輛從配送中心出發最終又返回配送中心。 13321807.每一個客戶點只能由一輛車進行服務，且客戶的需求量已知。 1318624（2）相關參數解釋 1314351（1）成本分析 1432637（2）約束條件 1553961.配送中心約束 15196752.客戶約束 15182583.配送車輛約束 154153（3）模型構建 16295812．表示從企業出發的車輛數目不超過K。 1668224．每條路徑上各個客戶點的需求量總和不得超過車輛最大載重量。 16206224.2遺傳算法設計與求解流程 1745934.3本章小結 21139255模型求解及優化結果分析 2264995.1遺傳算法求解對模型最優解的影響分析 2283955.2優化結果對比分析 23217865.3本章小結 2614166總結 2717754參考文獻 281研究的背景社會物流總費用由運輸費用、保管費用和管理費用組成。2020年社會物流總費用14.9萬億元，同比增長2.0%。社會物流總費用與GDP的比率為14.7%，與上年基本持平，其中，運輸費用7.8萬億元，增長0.1%；保管費用5.1萬億元，增長3.9%。管理費用1.9萬億元，增長1.3%。可以看出運輸費用占物流總費用的比重較大。因此，降低運輸成本能夠大大降低物流總成本，合理的車輛路徑計劃不僅能降低配送成本、提高配送效率，而且能提高客戶滿意度。科學合理的規劃車輛路徑方案，變得有尤為重要。我國大部分企業降低物流成本，是通過減少車輛數、提高裝載率和降低車輛行使路程，但是缺少將理論與實際結合的方法用來設計路徑安排。隨著計算機的發展，計算機算法成為路徑優化方案求解的主要方法，更加準確高效的推動物流業的發展。根據我國現有的物流操作模式，結合Y物流公司的實際運營情況，本論文是在這樣的背景下進行研究的。Y公司是一家主要從事物流服務的公司，公司處在一個快速發展的時期，客戶的數量隨著公司的不斷擴大逐漸增加，客戶對服務的要求越來越高，現有的配送路徑方案已經不能滿足客戶的需求，不適合企業的發展，客戶對服務的需求得不到滿足，造成客戶對公司的滿意度下降，退貨的情況時有發生。經過分析，導致出現這些現象的主要原因有：Y物流公司指定的配送方案配送路徑不合理，車輛行駛距離較長；Y物流公司車輛裝載不合理，大部分車輛的裝載率較低，車輛沒有充分利用；Y物流公司沒有滿足客戶的時間要求，造成客戶滿意度比較低。本文對Y物流公司的配送路徑進行優化。2研究的意義對車輛路徑優化問題進行研究，不但能夠應用到物流業，減少成本，而且能夠應用到制造業，如生產產品的生產和調度，車輛路徑優化問題可以處理企業存在的現實問題。隨著物流業的發展，人們越來越看重時效性，于是產生了帶時間窗的車輛路徑優化問題，比較接近現實工作與生活問題，并且能夠應用到不同的行業，去解決生產和調度產生的問題，直接給企業創造經濟價值和社會效益，對車輛路徑優化問題的研究有很高的理論價值和意義。具體的研究意義有：（1）降低物流公司配送成本物流公司從貨物的轉移中獲得大部分的利潤，配送過程產生的成本與物流公司的利潤息息相關。小規模的物流公司，客戶較少，車輛的配送路徑容易安排，但是大規模的物流公司，客戶點多，客戶的需求也多，依靠人工對車輛配送路徑進行調度，不僅配送效率低，而且配送路徑很容易不合理。利用計算機進行合理的優化建模，用不同的算法進行求解，能夠得到比人工調度更快，更合理的配送方案。合理的配送方案，用更少的車輛完成配送任務，能夠減少配送成本提高利潤。（2）提高客戶的滿意度隨著物流業的發展，客戶對物流服務要求越來越高，對物流客戶來說，滿意度主要體現在能否按時送達，如果在要求的時間窗內送達，客戶的滿意度最高，如果不在要求的時間窗內送達，客戶滿意度會降低，因此，通過算法搜尋最優的路徑優化方案，合理的規劃配送路徑，企業能夠以較少的成本，在客戶要求的時間內送達，客戶的滿意度大大提升，能夠獲得更多的客戶，提高企業的競爭力。通過對帶時間窗的路徑優化問題的研究，更符合客戶的服務要求，對提高客戶滿意度具有重要的意義。（3）提高車輛裝載率在進行路徑優化的建模過程中，以成本最少為目標，加入車輛裝載量的約束條件，基本能夠實現車輛滿載的效果。不僅縮短了車輛從配送中心到客戶的行使次數，而且車輛很容易達到滿載。（4）提高社會效益合理的路徑優化，減少了不必要的路程，能夠節約自然資源，緩解城市交通的壓力；減少了行使車輛的數量，不但能夠減少汽車尾氣排放，降低城市的噪音，更能實現低碳環保的理念。3Y物流公司車輛路徑現狀及問題分析3.1Y物流公司簡介Y物流集團有限公司總部在河南省鄭州市，是國家AAAA級物流企業，于2003年正式成立，由河南省交通廳下屬的一個倉庫逐漸發展成為現在的股份有限公司，在河南的市場是在全國市場的70%，是一家主要從事零擔物快運、3PL的公司，通過對省市縣三級區域配送網絡的整合，根據貨物運輸的網絡節點，在關鍵地方建設營業網點，不斷完善零擔網絡覆蓋的深度和廣度，在全國的零擔物流市場中處于靠前的位置。物流服務主要采用公路對貨物進行，在全國建設了40多萬平方米的倉庫，擁有成熟的零擔快運網絡，網絡覆蓋河南、河北、陜西、湖南、湖北、山東、山西、安徽、江蘇、四川、浙江、江西等省市。圖3-1全國業務分布圖Figure3-1NationalbusinessdistributionmapY物流集團有限公司創建了集物流、商流、信息流、資金流、薪金流五流合一多業態融合的綜合性現代物流模式。其中供應鏈金融服務包括代收款業務和融資業務。代收貨款業務是和銀行合作一起研發線上資金管理系統，包括貨款歸集、清分結算和貨款兌付，主要應用在零擔物流、第三方物流和城市配送三個業務，做到線上和線下共同支付相結合。融資業務是利用于金融機構和銀行合作，為物流產業鏈的微小企業成立會員制度，并對微小的企業數據進行分析，對客戶的信用進行評定，之后與客戶建立信任關系，為微小企業提供貸款服務。Y物流集團有限公司在河南省內的貨物配送采用星型模式，能夠覆蓋到縣級。省外的配送模式是“集散+直達”軸輻射式組網模式，首先由配送中心進行客戶需求數據的處理，由配送車輛送到區域集散點，再由區域集散點的車輛送到各個營業網點或者客戶。Y物流股份有限責任公司還為客戶提供物流方案，倉儲管理、裝卸搬運、流通加工，供應鏈金融等服務。設計研發WM倉儲管理系統，可以作為第三方物流公司為制造業、商貿流通業提供物流服務，包括倉儲、分類包裝和配送服務，還可以根據客戶的不同需求提供個性化的物流服務。圖3-2代收貨款業務圖Figure3-2Businesschartofcollectionandpayment圖3-3融資業務圖Figure3-3Financingbusinesschart圖3-43PL業務流程圖Figure3-43PLbusinessflowchart3.2Y物流公司車輛配送路徑運行現狀本文研究的主要是Y物流公司為某電商公司提供專業的3PL服務。通過更高效的運營模式，提高物流服務能力客戶的滿意度的同時，最大程度的降低配送的總成本。此次研究不只是節約運輸費用，更加在于可持續的降低物流的總成本。跟其它同類型的零擔物流企業一樣，Y物流公司的客戶分散在全國各地配送貨物的種類多、批次小，客戶對配送的質量和準時性的要求越來越高，零擔企業之間的競爭越來越大。以Y物流公司為某電商企業提供第三方物流配送服務為研究對象，以鄭州市的配送中心為出發點進行貨物運輸，運輸方式主要為公路運輸。運輸貨物主要為日用品和食品。Y公司現有的相應的配送線路運行卻是較為簡單的，具體的運行情況可以從Y物流公司的車輛、運價信息，Y物流公司配送線路情況等方面來依次分析和了解。3.2.1Y物流公司車輛、運價信息Y物流公司3PL業務各配送網點在進行配送活動時，用于為客戶提供配送服務的車輛為統一型號的貨車，車輛如表3-1所示，貨車最大載重量為3t，車廂容積為15立方米，公司配送的主要為一些日用品和食品等，一般都可以混裝，沒有重量很大體積很小的物品，且貨物都有包裝盒，在進行配送時不會出現為超過車輛最大載重量車輛就被裝滿的情況，因此計算貨物量時可以直接用體積表示，不需要考慮重量影響。Y物流服務公司白天的集中配送時間在中午11點至13點之間，公司安排小型車輛在白天對客戶進行物流服務，本文僅研究集中配送時段的配送方案，不考慮白天單獨補貨情況。表3-1配送車輛情況表Table3-1Distributionvehiclecondition車輛總數/（輛）型號速度/(km/h)容量/（㎡）單位成本（元/km）144.2501553.2.2Y物流公司車輛配送路線情況目前，Y物流公司3PL業務的配送路線，以鄭州市配送中心為出發點的客戶的貨物由司機親自送貨至對應的送貨點，一共分布了14家Y物流公司目標客戶。為了方便描述14個客戶點，將一個配送中心和14個客戶進行編號，鄭州市的配送中心由0表示，14個客戶點由1-14表示。以配送中心和客戶點的經緯度為坐標，客戶點的經緯度如表3-2所示，得到Y物流公司的配送網絡圖，如圖3-5所示：表3-2客戶點的相對坐標Table3-2Therelativecoordinatesofthecustomerpoints客戶經度緯度0113.89428734.7104321113.87239735.2971042113.66859735.2772643113.34420135.0716524114.06467635.3829365114.66280835.1824716113.43167835.2466347113.05984235.1696008112.80767935.5101719112.42598935.48313310113.68998535.46946811112.95220535.77530212113.30412835.79593913112.91348135.50955314112.83115835.479632圖3-5配送路線網絡圖Figure3-5Distributionroutenetwork由配送中心和客戶點的坐標得到配送網絡圖，只能得到之間的直線距離，不能用經緯度來計算之間的距離，實際的配送線路要考慮各種情況，利用地圖的導航功能和司機的經驗，進行各個客戶點距離的計算，得到彼此的距離表。表3-3各個客戶點間的距離Table3-3Thedistancebetweencustomerpoints距離0123456789101112131400166.30276.819.003116.036.431.104132.538.648.936.20590.0100.6110.799.271.50690.036.421.658.266.8129.707117.081.866.988.3108.3179.146.508165.8135.4117.3146.5155.1224.792.070.409204.8178.0156.3187.6194.1263.6131.0109.442.6010238.1212.0189.6220.9227.4294.7164.3142.775.941.3011190.4114.0142.0173.3179.8247.1116.795.044.682.485.7012220.9114.096.296.5125.9263.399.0119.175.0107.9120.347.1013158.2119.8109.8132.3147.6214.984.562.811.353.586.935.260.8014168.1129.7114.8142.2157.4224.889.280.25.742.175.647.2789.90當Y物流公司的配送車輛到達客戶點時，進行貨物的清點、裝卸搬運、檢查是否破損需要一段服務時間，Y物流公司的物流服務時間，由車型和貨物的多少決定，由于鄭州市的配送中心進行配送服務，車型一樣都是小型的貨車，裝貨量相對較小。規定每個客戶的服務時間不超過15分鐘。整理2019-2020年中間一年業務的需求量、期望配送時間以及每個需求點的服務時間如表3-4所示：表3-4客戶的需求量、期望配送時間以及所需服務時間Table3-4Customerdemand,expecteddeliverytimeandrequiredservicetime客戶行使路徑時間窗上限/min時間窗下限/min服務時間/min需求量/㎡10→1→075105154.320→2→0115145154.730→3→0155185157.5340→4→0160190155.1150→5→0120150158.9760→6→0145175158.3170→7→0155185155.2280→8→0215245157.2490→9→0245275154.91100→10→0315345158.94110→11→0195240158.86120→12→0255285154.99130→13→0165195158.57140→14→0175205154.923.3Y物流公司車輛路徑存在的問題及原因隨著Y物流公司業務規模的逐漸擴大，下層配送網點數量以及客戶數量也在不斷增加，與此同時客戶對配送服務的要求也越來越個性化和多樣化，最明顯的要求就是客戶對配送服務的時間要求越發苛刻。這使得公司進行貨物配送受到了更多的約束，公司制定配送方案難度也不斷提高，配送方案也變得更加復雜，配送成本隨之不斷增加。與此同時，配送車輛有時不能準時將貨物交至客戶手中，客戶對公司服務的滿意程度不斷下降，甚至常有投訴情況發生，最終甚至會達到放棄本公司選擇其他物流公司的情況，直接影響公司的信譽和業績。3.3.1Y物流公司車輛路徑存在的問題（1）物流配送成本大當Y物流公司接到客戶訂單時，配送中心的調度人員根據自己的經驗，安排人員進行配送。盡管調度人員有豐富的路線安排經驗，線路較少時能夠達到配送效果最優，但當配送線路較多時，調度人員很難規劃最優的配送線路。即使調度人員在進行路徑安排時考慮配送的距離、時間、交通和貨物的需求量，還是很容易出現配送線路高度重疊的現象，用較多的車輛進行貨物的配送，導致配送效率低，配送成本高。從上述路徑規劃方案可以看出在貨量較少時，經過計算一輛車可以完成兩個相近地點的配送，使用兩輛車進行配送，配送線路交叉重疊，增加物流成本。Y物流公司雖然強調信息化建設，但是需要投入大量的資金，導致實施不到位，仍然使用傳統的配送路線規劃，配送成本高，企業的利潤低，阻礙企業得發展。（2）配送服務水平低Y物流公司的配送服務水平較低，一方面體現在貨物不能在客戶要求的時間內送達，另一方面體現在貨物出現破損。配送中心的調度人員根據自己和司機的配送經驗，按照客戶的地理位置、貨物需求量對配送路線進行簡單的規劃，安排司機配送貨物。司機在配送的過程中，沒有對車輛進行實時的跟蹤查詢，只有在司機將要超過客戶要求的時間時，調度人員才會與司機進行溝通，查詢并解決超時的問題，企業和調度人員對配送時效不重視，對配送車輛的管理不到位，導致配送時間長、配送效率低。貨物的裝卸是由司機完成，司機沒有專門學習裝卸貨物的知識，經常發生貨物破損的情況，有時破損不是司機造成的，但由于司機沒進行報備，也要有一定的賠償，造成客戶的體驗差，配送服務水平低。（3）貨物裝載率低Y物流公司3PL業務在2019-2020年的平均裝載率不到50%，車輛的裝載率低。一方面體現在司機對多個客戶點進行配送時，調度人員沒有制定合理的裝貨順序和配送順序，導致一部分的貨物需要進行多次的裝卸，很容易遭到損壞，物流服務的時間也會相應的變長。另一方面車輛的裝載量不平衡和客戶點的需求不均衡，調度人員簡單的計算之后，制定車輛的配送路線，安排車輛配送，造成車輛裝載量不平衡，配送效率低。3.3.2Y物流公司車輛路徑存在問題的原因（1）配送計劃時間不合理Y物流公司的信息化水平較低，大部分員工的學歷是大專，掌握的知識和經驗不能滿足客戶需求的增加。Y物流公司車輛在進行配送時僅使用專業化的平臺監控系統，只能查詢車輛轉載貨物是否在客戶規定的時間段到達客戶點，使用功能有限；未使用GPS全程追蹤系統，不能進行車輛的實時定位，掌握車輛的行使狀況，配送中心、客戶點、調度人員和配送人員之間沒有實時溝通的信息平臺，只能通過電話進行溝通。配送計劃時間不合理，導致配送時效差、服務水平低。而利用計算機或是相應的配送調度系統來進行配送路徑的安排，制定快速，因為這能對大量數據資料進行快速的綜合加工和處理，可以輔助快速實現配送工作的優化管理，另外借助于信息系統的支持，企業的配送成本將有可能得到很大程度的降低。（2）路徑規劃缺乏科學方法Y物流公司對配送路線的規劃不夠重視，物流成本高和利潤低，物流成本大部分由配送成本構成。配送中心的調度人員根據經驗制定配送線路，沒有使用專業的工具對配送路徑進行規劃，在短時間內對客戶位置、貨物量、車輛數、交通路線綜合考慮，完成配送路線的規劃，容易造成配送路線重疊，配送時間長。調度人員進行路徑規劃，人工的規劃能力有限，計算、設計和安排司機配送貨物，經歷的時間長，響應時間慢，不能夠應對突發貨物需求的增長。配送路線規劃采用人工的方法，未使用科學的規劃方法，制定合理的配送路徑，導致服務水平和裝載率低。用科學的方法制定適合Y物流公司的路徑優化方案，高效率的將貨物送到客戶的手中，減少車輛的行使路線，降低配送成本，提高裝載率和服務水平，客戶滿意度會逐漸增強。Y物流公司想要進一步加強內部管理，降低配送成本，Y物流公司只有選擇合理的配送路徑制定方法，縮短配送計劃制定時間，加快對客戶的響應度，優化企業配送資源，升級企業配送管理機制，在客戶規定的時間內配送貨物，不斷完善配送服務。3.4本章小結本章通過對Y物流公司管理狀況和配送流程進行介紹，根據實際情況指出Y公司在配送過程中存在的問題，包括Y物流公司配送成本高、配送服務水平低、裝載率低等問題，分析產生這些問題的原因是配送計劃制定時間不合理和缺乏科學的路徑規劃。利用科學的方法對車輛配送路徑進行優化，只有這樣才能降低企業運營成本，提高服務水平，提高企業競爭力。4Y物流公司車輛路徑優化模型構建4.1Y物流公司車輛路徑優化建模4.1.1Y物流公司車輛路徑問題描述Y物流公司平常的工作是為客戶提供物流服務，根據客戶的要求將貨物從配送中心配送到各個需求點，用最少的成本高效率的完成配送任務。本文主要研究的是Y物流公司在實際運行中的路徑優化問題，將物流配送成本最低作為車輛路徑規劃目標。Y物流公司的車輛路徑問題的描述是：有一個能夠存儲貨物的配送中心，其中配送中心的位置已知，有一定數量的車輛，車輛的型號和裝載量一樣，從配送中心出發對客戶點進行貨物的配送，客戶點的位置和要求的時間窗已知，每個客戶點只能有一輛車進行服務，配送車輛要在要求的時間窗內對客戶進行服務；配送車輛完成所有規定的任務后必須返回配送中心。合理規劃車輛的配送路徑，在滿足所有約束條件下，達到總配送成本最小。4.1.2模型假設與參數設定車輛路徑問題需要配送中心綜合各種信息對配送路線進行合理規劃，確保物流配送成本最小化。為了達成以上目標，根據上一小節的問題體描述可做以下基本假設：（1）模型的假設本章構建模型的目標是配送總成本最小，配送總成本由運輸成本和違反時間窗成本構成。與運輸成本有關的要求包括，車輛的裝載量是有限的，在不超載的情況下，滿足客戶點的需求，車量從配送中心出發完成配送任務后需要返回配送中心，一輛車能夠為多個客戶點進行服務，但是一個客戶點只能由一輛進行物流服務，配送中心的貨物能夠滿足客戶點的需求，但是存儲貨物的數量是有限的，客戶點的庫存是一定的，需求也是有現的。與時間窗相關的要求包括，車輛對客戶點進行物流服務，需要在規定的時間內完成，早到和晚到會產生相應的懲罰成本。客戶點接受物流服務的時間有限制，配送車輛早到，需要等待到客戶規定服務的時間，增加車輛的等待成本；車輛晚到，不但降低客戶的滿意度，而且會影響下一個客戶點的配送。因此減少成本不但要減少車輛運輸成本，還要保證車輛在客戶要求的時間窗內進行服務，滿足客戶的時間窗要求，達到總成本最少、客戶滿意度最大的目標。為了滿足上述目標。具體的模型假設如下:1.假設配送車輛行駛速度已知且恒定，不考慮路上的交通擁堵狀況。2.配送中心和客戶點的位置已知，配送中心的貨物可以送達所有客戶。3.車輛從配送中心出發最終又返回配送中心。4.不同客戶點需求的貨物可以由同一輛車配送，即同一車輛可以混裝。6.兩個客戶點之間的距離同時考慮高德地圖上查詢的行駛路線和司機的行使經驗，結合兩種方案后選擇最恰當距離計算。7.每一個客戶點只能由一輛車進行服務，且客戶的需求量已知。8.配送中心的產品數量能夠滿足所有客戶的需求，一輛配送車輛可以同時為多個客戶服務。（2）相關參數解釋基于上述問題描述和假設的提出，本研究構建模型時使用的參數及其含義如下表所示。表4-1模型中的符號定義Table4-1Symboldefinitioninmodel符號定義函數的目標值企業需要服務的客戶數配送所需的車輛數車輛的額定容量客戶需求量和時間懲罰系數，其中表示配送中心，表示客戶點從點到點對應配送成本表示車輛從客戶點到客戶點，是0，1變量表示車輛開始對客戶進行服務的時間表示在客戶所需的服務時間表示車輛從配送中心到達客戶的行駛時間表示車輛從客戶到達客戶的行駛時間車輛可以訪問客戶所開始的時間車輛可以離開客戶所開始的時間4.1.3模型構建本文構建的路徑優化模型，以配送總成本最小為目標的單目標函數，考慮車輛的運輸成本和違反時間窗的成本。構建配送產生的總費用函數。構建模型的具體內容如下：（1）成本分析本文考慮客戶規定車輛送達的時間是一個時間段，不是時間點，在車輛路徑優化的過程中，需要達到客戶的要求，客戶的滿意度有很多的影響因素，包括貨物的質量和車輛配送的速度等，在構建模型時客戶的滿意度用物流服務的時間是否在規定的時間窗內，車輛路徑在進行優化時，以配送總成本最低為目標，違反時間窗產生的懲罰成本是重要的組成部分，因此車輛要盡可能的在時間窗內送達。為了更好的定義懲罰成本，首先定義一些參數：假設客戶期望獲得服務的時間段為，任務的實際開始的時間為。提前到達的懲罰因子為，延期達到的懲罰因子為，根據實際經驗得知，通常。當時，表示配送任務提前到達，則產生的懲罰成本為；當時，表示配送任務延期完成，則產生的懲罰成本為。有上述可知，懲罰成本函數可定義如下： （4-1）在進行路徑優化時，懲罰成本與公司實際車輛的配送成本相適合，不宜過高，盡可能地減少違反時間產生的懲罰成本。對于Y物流公司來說，按照如果持續遲到一個半小時，客戶的滿意度受到嚴重的影響，放棄與Y物流公司進行物流合作，此時設置懲罰成本為此次配送成本的60%；當車輛早到時，客戶的滿意度也會受到影響，此時的影響較小，設置懲罰成本為配送成本的20%；根據數據計算車輛的平均配送成本為450元，根據以上內容，本文設定遲到懲罰系數為3元/min，早到懲罰系數=1元/min。根據以上成本分析，本文的車輛路徑優化模型總目標函數可以表示為式： （4-2）（2）約束條件1.配送中心約束對配送中心的約束是，配送中心所有的車輛從配送中心出發到達客戶點，完成配送服務，最后要返回配送中心，保證車流量的平衡。2.客戶約束對客戶的約束條件包括：配送中心擁有的車輛僅有一輛，能對其中的一個客戶進行服務，一輛車可以為多個客戶提供服務，一個客戶只能有一個車輛進行服務；對于客戶點來說，車輛對其進行配送服務結束之后離開客戶點，對客戶點進行服務的車輛數和離開的車輛數要一致，保證車流量的平衡。配送車輛約束第一個是裝載量約束，裝載量約束是指配送中心的所有車輛從配送中心裝載貨物，到達每一個客戶點時，其中在進行配送的所有時間都不能超過車輛最大的裝載量。由于配送貨物體重比較輕，體積較大，本文只考慮不超過車輛最大的體積，不包括車輛最大的重量。第二個是數量約束配送中心的車輛除了體積的約束之外，還有數量的約束。在現實中配送中心能使用的車輛是有限的，不能超過擁有的車輛數，且每輛車服務的客戶數不超過客戶數之和。在進行路徑規劃時，盡量用較少的車輛進行配送，降低成本。（3）模型構建1．每個客戶點的配送需求只能由一個車輛配送，不可有第二輛車對該客戶進行服務。 （4-3） （4-4） 2．表示從企業出發的車輛數目不超過K。 （4-5）3．配送車輛在進行配送任務時不參與取貨活動，完成任務后直接返回原配送中心。 （4-6） （4-7）4．每條路徑上各個客戶點的需求量總和不得超過車輛最大載重量。 （4-8）5．對于車輛來說，是否從客戶點到客戶點，，車輛從客戶點到客戶點，否則為0。 （4-9）其中，公式（4-2）表示Y物流公司車輛路徑優化問題的目標函數：公式（4-3）、（44）表示每個客戶僅能被訪問一次；公式（4-5）表示從企業出發的車輛數目不超過,公式（4-6）、（4-7）保證每一輛車都從企業出發，最終又回到企業，保證流的平衡；公式（4-8）表示車輛要滿足容量約束；公式（4-9）是整數化約束，表示車輛是否要從客戶點到客戶點。4.2遺傳算法設計與求解流程4.2.1遺傳算法求解設計用遺傳算法在Matlab上求解配送路徑優化模型時，需要提前對遺傳算法進行設計，使其更好的融入需要解決的問題，從而求得該問題的近似最優解。首先確定運行參數種群規模、交叉概率、變異概率、終止條件，再經過編碼、確定初始種群、選擇、交叉、變異、適應度評價這一系列步驟后求得問題最優解。（1）編碼操作編碼是將實際路徑優化問題轉化為計算機能夠識別的語言，使用遺傳算法對路優化問題求解時，首先對問題進行編碼，配送路徑優化問題的編碼是配送中心和客戶點不同順序的組合，用計算機能夠識別的語言表示出來。因本研究求解Y物流公司配送問題的客戶點有14個，為了提高求解的效率和有效性，選擇自然數編碼方式，0代表配送中心，1-14為14個配送點。兩個0之間的路徑代表子路徑，表示配送車輛從配送中心出發，完成任務后又返回配送中心。如0，14，13，12，0，11，10，9，8，0，7，6，5，4，0，3，2，1，0。表示第一輛車裝滿貨物后從配送中心出發，經過14，13，12這3個客戶點后再返回配送中心；第二輛車經過11，10，9，8這4個客戶點后返回配送中心；第三輛車的配送路徑為7，6，5，4；第四輛車的配送路徑為3，2，1；其中每一個不同路徑上的客戶點順序是一定的，不能變換各自的順序，如果變換順序目標函數的值會受到影響。（2）生成初始種群生成初始種群是為了后面種群迭代的基礎，選擇初始種群的規模一般在30-200個中間。如果種群規模太小，在后續迭代中容易陷入局部最優；如果種群規模太大，會增加后續適應度值計算的難度，降低整體的計算速度，搜索最優解的范圍會增加，求得最優解的效率會降低，能夠防止搜索最優解時過早收斂。因此，要選擇恰當的初始種群。本研究一共有14個客戶，將種群規模設定為50。在初始種群時，首先產生第一的數為0的N+k-1個數的數列，染色體的數列是由0-N+k-1個數不同排列組合，其次將數列中大于N的數設置為0，生成多個子路徑，使用0將各個子路徑分開，其中如果產生了連續多個0，0和0之間不需要車輛進行配送，0表示配送中心，不會影響劃分各個子路徑的過程。不斷地的進行上述過程，直到生成所需要種群的規模。（3）適應度函數遺傳算法對路徑優化模型進行求解時，適應度函數用來判斷染色體的優劣，適應度值越大染色體越優秀，被保留下來遺傳給下一代的概率越大；適應度越小染色體被遺傳給下一代的概率越小。適應度值可以體現染色體是否接近最優解。適應度函數可以直接是路徑優化模型的目標函數，或者將目標函數子先進行變形再作為適應度函數。本文Y企業配送路徑優化問題的目標是配送途中成本和時間成本的總配送成本最小化，目標函數的值越小，越接近問題的最優解，其中目標畫數值最小的染色體即對應為Y企業配送路徑優化的最優方案，本文直接將Y物流公司配送路徑優化問題的目標函數作為適應度函數。根據上述路徑優化模型可以得到，Y企業配送路徑問題的適應度函數為該模型的目標函數。（4）選擇算子選擇的依據是適應度函數，計算每一個染色體的適應度函數值，染色體的適應度值越大，表示染色體的適應度越好則染色體的質量好，能夠將優秀的基因保留遺傳給下一代，生成適應度值更大的染色體，隨著不斷地迭代，越來越接近最優解，目前，主要的選擇形式有適應值比例選擇、排序選擇、精英選擇策略等。本文的適應度函數為目標函數，目標函數值越小越好，選擇的方式是將將適應度值較小的個體替換適應度大的個體，重復此操作，直至生成同等規模的新種群。（5）交叉算子交叉的過程是按照規定的交叉概率，隨機選擇兩個染色體的一些位置，此位置的基因作為交叉點，兩個染色體按照交叉概率進行交叉，彼此交換交叉點的基因，形成兩個新的染色體，進而產生新的種群。本文設置的交叉概率為，將父代種群，按照此交叉概率，隨機且不重復的選擇兩個染色體將交叉點的基因片段的進行交換，完成交叉操作。假如父代兩條染色體的基因片段為A=2-6-3-7-1-4-8-9-5，B=7-5-8-1-3-6-2-9-2。隨機概率產生的交叉點分別為6，8；5，2。則交叉區域就變成A=2-6|3-7-1-4|8-9-5，B=7-5|8-1-3-6|2-9-2。A1=|3-7-1-4|，B1=|8-1-3-6|,則在A中刪除與B1中重復的基因，再把B1基因全部添加到A相應的基因片段中。例如A=2-6-3-7-1-4-8-9-5，B1=|8-1-3-6|，刪除后A剩下的為2-7-4-9-5，把B1基因全部添加到A相應的基因片段中,那么A的新基因就變成了2-7-|8-1-3-6|-4-9-5。接下來對于B染色體也執行同樣的操作，從而形成新的子代種群進入下次迭代。（6）變異算子遺傳算法的變異操作是模仿自然界中基因的變異，是將父代染色體的基因用別的基因替代，生成新的不同序列的子代染色體。選擇和交叉能夠保證遺傳算法的全局搜索性能，變異能夠保證遺傳算法的局部搜索性能，選擇、交叉、變異共同保證了遺傳算法搜索的優性。染色體根據變異概率進行變異，Y物流公司路徑優化模型的求解，選取的變異概率為變異的方式有互換變異算子、逆轉變異算子、均勻變異算子等，本文遺傳算法研究選取了逆轉變異。假設：父代A為439165872，如果變異概率產生的變異點為(4，6)，表示該染色體基因的第四位和第六位發生變異，將染色體基因的第四位到第六位按照逆序進行排列，生成新的子代染色體為439561872。進行變異的操作之后，分別計算父代和子代染色體的適應度，如果子代更優秀則將子代替換父代，如果父代更優秀，變異失敗繼續選擇父代進行迭代。（7）終止條件在用遺傳算法進行配送車路路徑優化問題求解時，終止遺傳算發的方式有迭代得到最優解在之后的次之后未改進，或者規定在迭代次之后得到最優解終止迭代，本文選擇迭代次數達到最大迭代次數450次終止遺傳算法，并輸出最優解。4.2.2遺傳算法的求解流程遺傳算法求解思路，經典的遺傳算法流程圖4-1所示，遺傳算法利用三個遺傳算子進行求解，當終止條件滿足時，達到最大循環次數，于此同時最優個體不再進化。圖4-1遺傳算法求解流程圖Figure4-1Flowchartofgeneticalgorithm遺傳算法的求解過程主要包括以下步驟。第一步：首先將車輛路徑優化的實際問題轉化成計算機能夠識別的問題，其次選擇合適的編碼方式，確定實際問題的參數集，對參數集進行編碼，構造適合該問題的染色體。當對現實問題對染色體進行編碼時，應該選擇適合構建模型約束條件的編碼方式，能夠提高計算的速度和效率。第二步：首先篩選被編碼的染色體，隨機產生初始種群，形成一組初始的染色體，初代染色體的數量應該合理設置，其次設置初始迭代次數，確定該問題適應度函數；第三步：根據第二步中確定的適應度函數，計算每個染色體的適應度值，染色體的優劣根據適應度值進行判斷，適應度值大的染色體越接近最優解；第四步：經過第三步計算染色體的適應度值之后，將染色體進行選擇、交叉、變異的操作過程，再進行解碼計算適應度值，選擇適應度值大的染色體，進行新一輪的迭代，父代染色體在進行選擇、交叉、變異一系列操作后，產生新的子代染色體，種群不斷地進行迭代；第五步：不斷地繼續地進行第四步直到滿足迭代次數到達終止次數，停止迭代。當第四步迭代地次數小于終止條件地迭代次數時，繼續進行迭代；當第四步迭代地次數大于終止條件地迭代次數時，終止迭代，進行第六步；第六步：迭代次數達到終止條件，停止迭代，計算并輸出迭代的最優結果。4.3本章小結本章首先對Y物流公司現存情況進行假定的基礎上建立了一個目標函數即總配送成本最小化路徑優化數學模型，配送總成本包括車輛的配送成本和違反時間窗的懲罰成本，然后在對遺傳算法的基礎上，通過對染色體編碼、確定初始種群、適應度函數、遺傳算子和算法終止條件等進行了設計，運用遺傳算法通過matlab對此模型進行求解，此章為第五章的求解分析提供理論與技術支持。5模型求解及優化結果分析5.1遺傳算法求解對模型最優解的影響分析根據配送優化方案，進行優化配送路徑，并利用Matlab編程求解，將構建模型需要的數據帶入，運行450次后終止運行，程序運行10次的目標函數值和收斂的迭代次數如圖5-1所示，分析遺傳算法的選擇算子、交叉算子和遺傳算子對Y物流公司目標函數值的影響。圖5-1運行次數圖Figure5-1operationtimes（1）選擇算子根據圖5-1所示，利用matlab運行程序10次的結果顯示，種群迭代在100代附近開始收斂得到模型的最優解，每次運行的結果相差比較小，并且算法的收斂速度快。選擇算子用種群中適應度值最低的代替適應度高的個體，適應值低的個體具有較大的被選擇的概率，保證了種群中最優的個體能夠進行復制將優秀基因遺傳給下一代，這種選擇的方法使得適應度高的個體沒有被被淘汰的可能，如均勻分布選擇法、輪盤賭選擇法和錦標賽選擇法均是利用概率進行選擇，使得適應度高的個體也有被淘汰的可能。（2）交叉算子在用遺傳算法進行求解時，選擇和交叉算子能夠保證遺傳算法的全局搜索能力，交叉算子作為全局搜索能力的主要算子，利用交叉算子全局搜索最優解，使用兩點交叉算子進行計算，如圖5-1能夠得到較好的效果。（3）變異算子遺傳算法的變異算子保證了其局部搜索最優解的能力，當交叉算子進行全局搜索接近最優解時，用變異算子局部搜索最優解，能夠加快遺傳算法的收斂質量和效率，選擇逆轉變異作為本文的變異算子，快速得到了建立模型的最優解，根據圖5-1所示，利用逆轉變異進行遺傳算法的變異算子，沒有出現過早收斂的現象。5.2優化結果對比分析利用遺傳算法并用Matlab編程求解可以得到14個的最優的配送路線，根據上一節的求解結果，選擇其中費用最少的一次求解結果與未優化的結果進行對比分析，遺傳算法迭代曲線及優化結果如圖所示：圖5-2遺傳算法求解的配送路徑示意圖Figure5-2Distributionroutediagramsolvedbygeneticalgorithm圖5-3遺傳算法求解的迭代圖Figure5-3Iterativegraphsolvedbygeneticalgorithm路線安排由迭代曲線可以看出，設計的遺傳算法迭代到100次后基本保持穩定，目標函數值不會發生變化，據此可以驗證模型具有有效性，生成最優配送路線如表所示。根據車輛配送路線可以得到每輛車在配送過程中的實際貨物載重量以及行駛時間、配送總成本。將配送方案進行優化后的結果與Y物流公司之前進行比較，并從配送成本、車輛投入、車輛滿載率等方面進行效果分析。Y物流公司集中配送的總成本是20349元，其中用到車14輛、平均滿載率分別為44%，如表所示，現結合Y物流公司日常集中配送情況，將優化后日的配送情況與當日優化前配送情況做對比，比較結果見表：表5-1優化前的配送信息Table5-1Distributioninformationbeforeoptimization路徑序號配送順序行駛距離/km行駛時間/min實際容量/㎡額定容量/㎡實載率/%10→1→0132.60174.124.3150.2920→2→0153.60199.324.7150.3130→3→0232.00293.407.53150.5040→4→0265.00333.005.11150.3450→5→0180.00231.008.97150.6060→6→0180.00231.008.31150.5570→7→0234.00295.805.22150.3580→8→0331.60412.927.24150.4890→9→0409.60506.524.91150.33100→10→0476.20586.448.94150.60110→11→0380.80471.968.86150.59120→12→0441.80545.164.99150.33130→13→0316.40394.688.57150.57140→14→0336.20418.444.92150.33表5-2優化后的配送信息Table5-2Optimizeddistributioninformation路徑序號配送順序行駛距離/km行駛時間/min實際容量/㎡額定容量/㎡實載率/%懲罰成本/元10→1→6→0192.70276.2412.61150.846.7620→12→8→0461.70599.0412.23150.81375.2430→14→13→0336.20448.4413.49150.89100.840→11→7→0402.40527.8814.08150.93517.4450→4→5→0294.00397.8014.08150.93329.460→9→10→0484.20626.0413.85150.924.6870→3→2→0223.90313.6812.23150.81139.56表5-3遺傳算法求解結果與優化前情況對比Table5-3Theresultofgeneticalgorithmiscomparedwiththatbeforeoptimization配送車輛/輛總行使距離/km總成本/元總行使時間/min平均裝載率/%優化前144069.8020349.005093.760.44優化后72391.5012329.823189.120.87（1）配送總成本為方便進行比較，本文僅對配送總費用進行對比。通過表5-3可以看出優化前配送費用為20349.00元。通過計算優化后的配送總費用為12329.82元，包括車輛行駛成本、提前達到等待時間成本、延遲到達導致的機會成本。優化后總成本較優化前減少了8019.18元，總體降低39%。Y物流公司不斷擴大在全國的業務范圍，對其配送路徑進行優化，可以減少Y物流公司在配送成本的投入，節約配送成本，增加配送效率，提高客戶滿意度，為公司未來的發展做鋪墊。（2）車輛滿載率由于現階段Y物流公司在配送路線基本固定，現有車輛的平均裝載率約為44％。經過優化配送方案，每輛車依次對客戶進行配送，不必局限于固定配送路線，避免路徑重疊現象，此時的車輛平均滿載率可達87%，較于優化前提升了49%。從配送車輛總數來看，優化之前共需要14輛車，在進行優化的情況下，只需要7輛車就能對14家客戶進行配送，使得配送車輛減少了7輛，車輛越少越管理越方便，使用次配送模式可以減少使用車輛，方便企業進行車輛調度，有利于提高配送質量和效率，增強Y物流公司在物流行業的競爭力。（3）配送總行使距離和時間優化前的總行使距離是4069.80km，優化后的方案是2391.50km,兩者差距為1678.3km，降低了41%；配送總時間由5093.76減少為3189.12，減少了38%，使用優化后車輛路徑配送方案，能夠明顯降低在配送過程中所消耗的時間和成本。5.3本章小結本章通過對Y物流公司配送的實際情況進行分析，利用遺傳算法對模型進行求解，在遺傳算法中，編碼不同對優化模型表現的精確性不同，優化模型包括多個參數，參數的不同設計會影響模型求解的結果，因此將本文的模型參數帶入算法進行運算，進而求解出從配送中心到14個目標客戶的最優配送路徑。通過對優化前后配送路徑信息的對比，可以證實此模型算法的科學性和有效性。同時該模型具有可塑性，在目標客戶數量、位置信息、需求量發生變化時，都可以通過改變對應數值通過此模型進行求解，得到更新后的最優路線信息，這對于科學高效規劃配送路徑，提高服務水平，提高配送質量有著極為重要的意義。456總結本文以從物流公司向客戶進行配送這一實際問題為研究背景，重點針對配送系統中的車輛路徑優化問題展開研究，采用遺傳算法作為優化工具，首先分析了車輛路徑問題的內涵與發展、建立了車輛路徑優化的數學模型，構建了以運輸成本和違反時間窗的懲罰成本作為目標函數的車輛路徑問題模型。針對該模型設計了相應的遺傳算法并對實際問題進行了求解優化。全文研究內容共包括以下部分：（1）在閱讀相關國內外文獻的基礎上，對車輛路徑問題和求解算法的國內外研究現狀進行歸納，重點研究了其中的車輛路徑優化問題并分析了帶時間窗車輛路徑優化問題和遺傳算法的研究現狀。給出了車輛路徑問題的基本描述、分類和構成要素，選擇遺傳算法為本文的優化工具，并對遺傳算法及其相關知識、原理和算法的實現方法進行了研究。（2）對Y物流公司配送中心向顧客進行配送這一實際問題進行了數學描述，做出了建模前的基本假設，建立帶時間窗的從一個配送中心向14個客戶需求點進行運輸的物流車輛優化問題的數學模型，將違反時間窗的懲罰成本和運輸成本之和作為目標函數，基于遺傳算法對從一個配送中心向14個客戶需求點進行產品運輸的物流車輛優化問題進行全局優化研究。（3）結合Y物流公司問題的數學模型進行了遺傳算法設計，主要包括遺傳算法編碼和選擇、交叉、變異算子的設計，通過適應度值較小的個體替換適應度大的個體，重復操作，直至同等規模的新種群形成。加快種群的收斂速度，使用兩點交叉算子和兩點互換變異算子，給出了遺傳算法的運算流程。使用MATLAB進行了遺傳算法的編碼計算。運用該算法Y物流公司問題的數學模型求解，求解結果比較穩定。（4）將遺傳算法得到的優化結果與未優化路徑相比，配送下成本節約39%，求解結果相較實際的配送方案有較好的優化效果，驗證了模型和算法的科學性和有效性，能夠為實際的配送問題提供更經濟合理的配送方案，遺傳算法設計的車輛路徑優化決策可以更好地節約配送成本，優化策略正確有效。參考文獻Dantzig,G.B.RamserJH.TheTruckDispatchingProblem[J].ManagementScience,1959,6(1):80-91.ClarkeG,WrightJ.Schedulingofvehiclesfromcentraldepottoanumberofdeliverypoints[J].OperationsResearch,1964,12:568-581.GillettB,MillerL.AheuristicalgorithmforthevehicledispatchProblem[J].OperationsResearch，2004,22:340-349.BodinLD,GoldenBL,AssadAA,etal.Routingandschedulingofvehiclesandcrews:thestateofart[J].Computers&OpcrationsRescarch,1983,(10):63-211.BakerBM,AyechewMA.Ageneticalgorithmforthevehicleroutingproblem[J].Computers&OperationsResearch,2003,30(5):787-800.Kolen,ComparisonofSystemsBasedonEvolutionarySearchandSimulatedAnnealingtoSolvetheVRTWProblerm.InternationalJournalofComputationalIntelligenceandApplications[J].2004,4(1):27-39.ChenP,HuangH,DongXY.Iteratedvariableneighborhooddescentalgorithmforthecapacitatedvehicleroutingproblem[J].ExpertSystemswithApplications,2010,37(2):1620-1627.RajeevG,RamanM.AhybridofAntColonyandfireflyalgorithms(HAFA)forsolvingvehicleroutingproblems[J].JournalofComputationalScience,2018(3):25-38.劉晉,亢耀先.車輛路線路徑問題的一種新的啟發式算法一二重優化法[J].北京郵電大學學報,1985(1):60-68.劉寶碇,趙瑞清,王綱.不確定規劃及應用[M].清華大學出版社,2003.王征,張俊,王旭坪.多車場帶時間窗配送路徑問題的變鄰域搜索算法[J].中國管理科學,2011,19(02):99-109.李寧.物流配送網絡規劃問題研究[D].北京:北京交通大學碩士學位論文，2011.麻存瑞,柏赟,趙欣苗,曾瑋.快遞配送車輛路徑優化研究[J].交通運輸系統工程與信息,2017,17(04):182-187.龐燕,羅華麗,邢立寧,任騰.車輛路徑優化問題及求解方法研究綜述[J].控制理論與應用,2019,36(10):1573-1584.李陽,范厚明,張曉楠.動態需求下車輛路徑問題的周期性優化模型及求解[J/OL].中國管理科學:1-12[2021-01-07].Kolen,A.Rinnooy,K.Trienekens,H.Vehicleroutingwithtimewindows[J].Operationsresearch,1987,35(2):266-73.Savelsbergh,M.LocalSearchinRoutingProblemswithTimeWindows[J].AnnalsofOperationsResearch.1985,16(4):285-305.Thangiah,S.Nygard,K.Ageneticalgorithmsystemfor