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

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

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

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

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

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

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