【VRP】基于matlab遺傳算法求解多車輛路徑規劃問題【含Matlab源碼 1249期】

1 VRP基本原理

車輛路徑規劃問題(Vehicle Routing Problem，VRP)是運籌學裡重要的研究問題之一。VRP關注有一個供貨商與K個銷售點的路徑規劃的情況，可以簡述為：對一系列發貨點和收貨點，組織調用一定的車輛，安排适當的行車路線，使車輛有序地通過它們，在滿足指定的限制條件下（例如：貨物的需求量與發貨量，交發貨時間，車輛容量限制，行駛裡程限制，行駛時間限制等），力争實作一定的目标（如車輛空駛總裡程最短，運輸總費用最低，車輛按一定時間到達，使用的車輛數最小等）。

VRP的圖例如下所示：

2 問題屬性與常見問題

車輛路徑問題的特性比較複雜，總的來說包含四個方面的屬性：

（1）位址特性包括：車場數目、需求類型、作業要求。

（2）車輛特性包括：車輛數量、載重量限制、可運載品種限制、運作路線限制、工作時間限制。

（3）問題的其他特性。

（4）目标函數可能是總成本極小化，或者極小化最大作業成本，或者最大化準時作業。

3 常見問題有以下幾類：

（1）旅行商問題

（2）帶容量限制的車輛路線問題(CVRP)

該模型很難拓展到VRP的其他場景,并且不知道具體車輛的執行路徑，是以對其模型繼續改進。

（3）帶時間窗的車輛路線問題

由于VRP問題的持續發展，考慮需求點對于車輛到達的時間有所要求之下，在車輛途程問題之中加入時窗的限制，便成為帶時間窗車輛路徑問題（VRP with Time Windows, VRPTW）。帶時間窗車輛路徑問題（VRPTW）是在VRP上加上了客戶的被通路的時間窗限制。在VRPTW問題中，除了行駛成本之外, 成本函數還要包括由于早到某個客戶而引起的等待時間和客戶需要的服務時間。在VRPTW中，車輛除了要滿足VRP問題的限制之外，還必須要滿足需求點的時窗限制，而需求點的時窗限制可以分為兩種，一種是硬時窗（Hard Time Window），硬時窗要求車輛必須要在時窗内到達，早到必須等待，而遲到則拒收；另一種是軟時窗（Soft Time Window），不一定要在時窗内到達，但是在時窗之外到達必須要處罰，以處罰替代等待與拒收是軟時窗與硬時窗最大的不同。

模型2(參考2017 A generalized formulation for vehicle routing problems)：

該模型為2維決策變量

（4）收集和分發問題

（5）多車場車輛路線問題

參考(2005 lim，多車場車輛路徑問題的遺傳算法_鄒彤, 1996 renaud)

由于車輛是同質的，這裡的模組化在變量中沒有加入車輛的次元。

（6）優先限制車輛路線問題

（7）相容性限制車輛路線問題

（8）随機需求車輛路線問題

4 解決方案

（1）數學解析法

（2）人機互動法

（3）先分組再排路線法

（4）先排路線再分組法

（5）節省或插入法

（6）改善或交換法

（7）數學規劃近似法

（8）啟發式算法

5 VRP與VRPTW對比

1 引言

2 遺傳算法理論

2.1 遺傳算法的生物學基礎

2.2 遺傳算法的理論基礎

2.3 遺傳算法的基本概念

2.4 标準的遺傳算法

2.5 遺傳算法的特點

2.6 遺傳算法的改進方向

3 遺傳算法流程

4 關鍵參數說明

1 matlab版本

2014a

2 參考文獻

[1] 包子陽,餘繼周,楊杉.智能優化算法及其MATLAB執行個體（第2版）[M].電子工業出版社，2016.

[2]張岩,吳水根.MATLAB優化算法源代碼[M].清華大學出版社，2017.