連鎖商業(yè)貨物配送中的車輛優(yōu)化調度模式研究及開發(fā)

1、1連鎖商業(yè)貨物配送中的連鎖商業(yè)貨物配送中的車輛優(yōu)化調度模式研究與開發(fā)車輛優(yōu)化調度模式研究與開發(fā)2連鎖商業(yè)貨物配送中的連鎖商業(yè)貨物配送中的車輛優(yōu)化調度模式研究與開發(fā)車輛優(yōu)化調度模式研究與開發(fā)一、一、研究背景研究背景二、優(yōu)化問題數(shù)學模型二、優(yōu)化問題數(shù)學模型三、三、解決的理論與方法解決的理論與方法四、四、軟件成果軟件成果3一、一、研究背景研究背景1、香港某連鎖店配送（、香港某連鎖店配送（1997年）年）分 店：240 (香港島，九龍半島，新界，其他)運輸車輛：64（6個車型：封閉、敞棚、低開等； 各種噸位）2、北京、北京某超市連鎖店某超市連鎖店（2000年）年）分 店：20余家（力求3-5年時間建成

2、50-100家）配送中心：五環(huán)外某處 運輸車輛：9（車型：大貨5噸、2.75噸； 小貨2噸、1.75噸； 北旅1噸）4 配 貨 中 心ABDCFEHGI車庫連鎖店配送示意圖連鎖店配送示意圖5一、一、研究背景研究背景要 求：（1）計算機給出派車單（在線，離線），提供車輛裝貨的方案和車輛行走的路線。（2）車隊的規(guī)模大小。主要考慮因素：（1）多個分店貨物的混裝；（2）分店裝卸時間窗口、車型的限制；（3）道路時間窗口、噸位的限制；（4）司機的工作時間限制，負荷均衡；（5）車輛平衡負載；等等6二、優(yōu)化問題數(shù)學模型二、優(yōu)化問題數(shù)學模型 2. 車輛路線問題車輛路線問題(vehicle routing)車輛行

3、駛路線最短車輛行駛路線最短 1. 裝箱問題裝箱問題(bin packing)多個分店貨物混裝問題，需求超出車載的多個分店貨物混裝問題，需求超出車載的分店裝車問題分店裝車問題 3. 匹配問題匹配問題(allocation)車輛總數(shù)，車型搭配，司機人數(shù)車輛總數(shù)，車型搭配，司機人數(shù) 4. 平衡問題平衡問題(balancing)司機的工作時間，車輛的行駛里程司機的工作時間，車輛的行駛里程7二、優(yōu)化問題數(shù)學模型二、優(yōu)化問題數(shù)學模型 6. 其他其他打折，贈送打折，贈送 5. 時間窗口問題時間窗口問題(time-window)供貨時間、道路限制供貨時間、道路限制各種復雜模型各種復雜模型(NP-Complet

4、e)的綜合集成的綜合集成v多目標優(yōu)化；連續(xù)/離散優(yōu)化；線性/非線性優(yōu)化以上問題必須考慮：道路限制、供貨時間限以上問題必須考慮：道路限制、供貨時間限制、車載量限制和配送中心調度員的調度時制、車載量限制和配送中心調度員的調度時間周期間周期8三、三、解決的理論與方法解決的理論與方法分解、協(xié)調優(yōu)化；啟發(fā)式、滿意解近似算法、貪婪方法等；近似算法、貪婪方法等；現(xiàn)代優(yōu)化、智能算法等（如現(xiàn)代優(yōu)化、智能算法等（如tabu search, simulated annealing, evolutionary algorithms, neural networks etc. )2. 路線問題路線問題(routing)

5、 v扇形法扇形法 、中心擴散等中心擴散等1. 裝箱問題裝箱問題(bin packing)vNF，WF，BF等等 9三、三、解決的理論與方法解決的理論與方法扇形法扇形法配 貨中 心ABDCFEHGI車庫10三、三、解決的理論與方法解決的理論與方法中心擴散中心擴散 配 貨中 心ABDCFEHGI車庫11主算法主算法 Step1(全局計算)若不是特殊店，按區(qū)計算未預裝且滿足車載限制的店“是否一定送貨”和“店級別”的加權和，從最大車輛開始，將車輛分配給最大權和的區(qū)域，直至全部需求店預裝或全部車輛派完。 （車輛數(shù)循環(huán)） Step2（區(qū)域計算）在每一個區(qū)域內，根據(jù)現(xiàn)有的店和分配車輛，q 2.1 根據(jù)車輛數(shù)

6、目并以始終點相同分別采用“insertion”算法，給出每車的預裝方案；q 2.2 若“一定送貨”店或“低”級別店得到送貨而“高”級別店沒有送貨，此時，根據(jù)“是否一定送貨”，“店級別”字典序排列店順序，按道路連通情況修正預裝方案；q 2.3 以每車可開始工作的最早時間分別計算每店的供貨時間表。輸出各車輛的裝車方案和各車輛可以再工作的開始時間。12主算法主算法 Step3 （全局計算）判別是否有未服務的店且車輛開始服務時間是否滿足再裝車要求。若有未服務的店且車輛滿足再裝車要求，則返回Step1. Step4 特殊店處理。選載重最匹配車輛。 Step5（全局計算）司機分配優(yōu)化。按車輛的最后一次預裝方案的一個店同司機家最近分配車輛。 Step6 （區(qū)域計算）將司機家作為一個店加入，以配貨中心為起點，司機家為終點，采用“insertion”算法再次優(yōu)化計算每一車輛的最后一次預裝店路徑優(yōu)化及計算每一店的送貨時間表。 Step7 （全