物流配送調(diào)度算法分析

1、1,物流配送調(diào)度算法分析,2020年12月31日,2,Topics,問(wèn)題描述 算法輸入條件分析 算法輸出分析 算法指標(biāo) 算法異常處理 算法框架 百度地圖接口調(diào)研,3,問(wèn)題描述,問(wèn)題背景： 1. 城市中有固定的貨運(yùn)公交站點(diǎn)，貨運(yùn)公交運(yùn)行于各個(gè)站點(diǎn)間，并且可在各個(gè)站點(diǎn)進(jìn)行裝貨和卸貨。 2. 通常在派發(fā)調(diào)度任務(wù)時(shí)，貨運(yùn)路線的信息是已知的。貨運(yùn)車輛的數(shù)量和車輛起點(diǎn)（位置）是已知的。但是車輛運(yùn)行時(shí)間和路線需要算法確定。 算法確定的車輛起始和終點(diǎn)是否可以不同？已經(jīng)解決：起始點(diǎn)與線路相同，終點(diǎn)可以設(shè)置（1,線路起始點(diǎn)，線路終點(diǎn)，可停車的站點(diǎn)）,4,問(wèn)題描述,3. 每個(gè)貨運(yùn)站點(diǎn)需要裝載或者卸載的貨物有重量、體

2、積、數(shù)量、性質(zhì)等信息，同時(shí)指定了的貨運(yùn)公交到達(dá)時(shí)間（貨運(yùn)公交車需要在此時(shí)間之前到達(dá)）。 4. 貨物送到貨運(yùn)站點(diǎn)然后再送到指定的客戶。 算法需要根據(jù)客戶地址確定該客戶訂單對(duì)應(yīng)的最近的貨運(yùn)站點(diǎn) 5. 調(diào)度任務(wù)通常一天會(huì)派發(fā)兩次（上午，下午各一次）。 算法運(yùn)行時(shí)間需要控制在2小時(shí)左右。（根據(jù)地圖規(guī)模，站點(diǎn)數(shù)量等指標(biāo)來(lái)確定。）,5,問(wèn)題描述,調(diào)度策略考慮的因素有： （1）各個(gè)貨運(yùn)站點(diǎn)的發(fā)貨信息和收貨信息、收發(fā)貨時(shí)間等。 （2）貨運(yùn)公交的信息； （3）道路信息；,6,問(wèn)題描述,調(diào)度策略滿足： 發(fā)出車量盡可能少，車輛裝載率高而空車率低，在滿足上述需求基礎(chǔ)上進(jìn)一步考慮車輛運(yùn)行里程的優(yōu)化。 裝載率=實(shí)際裝載量

3、/總裝載能力*100% 空車率=空車行走距離/配送的總距離*100%,7,算法輸入條件分析1.線路基本信息,8,算法輸入條件分析2.車輛設(shè)置,9,算法輸入條件分析 3.送貨策略設(shè)置（重點(diǎn)）,10,算法輸入條件分析4.伙伴排序依據(jù)（具體含義？,11,算法輸入條件分析5.契合時(shí)間窗的方式,12,算法輸入條件分析6.數(shù)據(jù)信息,6.1 運(yùn)單信息 貨物名稱、數(shù)量、體積、重量、發(fā)貨/收貨、常溫/冷藏、貨物屬性、產(chǎn)生時(shí)間、可接收時(shí)間、卸貨/裝貨耗時(shí)，起始站點(diǎn)、目標(biāo)站點(diǎn)。 相同類型的運(yùn)輸任務(wù)可以同車；可接收時(shí)間為目標(biāo)站點(diǎn)可以接收訂單的時(shí)間范圍。,13,算法輸入條件分析6.數(shù)據(jù)信息,6.2道路信息 名稱、地址范

4、圍、距離、單（雙）向、所屬區(qū)劃、交叉點(diǎn)。 道路級(jí)別及車速限制：州際、主干道路、次級(jí)道路、地方道路和坡道，各級(jí)別道路對(duì)應(yīng)的車速及浮動(dòng)量。 道路限制:車型限制、單行道、高峰時(shí)間、高峰時(shí)間、高峰時(shí)車速、封路區(qū)域、封路時(shí)間、車牌單雙號(hào)等 此部分信息需要從GIS數(shù)據(jù)中拿到。,14,算法輸入條件分析6.數(shù)據(jù)信息,6.3 站點(diǎn)信息 貨運(yùn)節(jié)點(diǎn)地理信息 節(jié)點(diǎn)的經(jīng)緯度值。 節(jié)點(diǎn)屬性 (取和送)。(出發(fā)節(jié)點(diǎn)、返回節(jié)點(diǎn)、其他)。 節(jié)點(diǎn)的車輛類型限制 m種車型。,15,算法輸出,16,算法指標(biāo),17,異常情況,18,算法框架,算法框架包括主要三個(gè)部分： 1.根據(jù)系統(tǒng)的運(yùn)輸線路設(shè)置和約束條件獲取該運(yùn)輸線路的伙伴站點(diǎn)。 2

5、. 根據(jù)伙伴站點(diǎn)的數(shù)量和約束條件確定運(yùn)輸?shù)能囕v。 3.根據(jù)車輛的運(yùn)單和約束條件對(duì)運(yùn)輸路徑調(diào)整。,19,算法框架,1.根據(jù)系統(tǒng)的運(yùn)輸線路設(shè)置和約束條件獲取該運(yùn)輸線路的伙伴站點(diǎn)。 計(jì)算每條線路從起點(diǎn)到終點(diǎn)的最短路徑。 用插入法比較加入一個(gè)新的運(yùn)單之后，最短路徑的變化，選擇最優(yōu)的站點(diǎn)進(jìn)入到路線中。 運(yùn)行一段時(shí)間之后可以將插入法和歷史數(shù)據(jù)結(jié)合考慮。從而獲取更加合適的伙伴集合。 重復(fù)上述過(guò)程得到各個(gè)線路對(duì)應(yīng)的運(yùn)單集合。,20,算法框架,2.根據(jù)伙伴站點(diǎn)的數(shù)量和約束條件確定運(yùn)輸?shù)能囕v。 對(duì)伙伴站點(diǎn)按照到達(dá)時(shí)間的先后排序，按照順序安排運(yùn)單，主要考慮的因素有： 運(yùn)單是否滿足時(shí)間需要； 運(yùn)單的距離因素； 車輛的裝載和空車； 需要定義一個(gè)約束函數(shù)來(lái)計(jì)算。,21,算法框架,3.根據(jù)車輛的運(yùn)單和約束條件對(duì)運(yùn)輸路徑調(diào)整。 在各個(gè)車輛的運(yùn)輸任務(wù)確定之后根據(jù)運(yùn)單的情況來(lái)確定最短路徑。此時(shí)問(wèn)題簡(jiǎn)化為旅行商問(wèn)題（TSP）。 考慮用啟發(fā)式算法，增加歷史數(shù)據(jù)的參考。 也可以對(duì)比各種經(jīng)典算法，選擇合適的。,22,百度開(kāi)發(fā)接口調(diào)研,基本數(shù)據(jù)信息有，沒(méi)有找到的信息： 各級(jí)別道路對(duì)應(yīng)的車速及浮動(dòng)量。（需要落實(shí)） 道路限制:車型限制、單行道、高峰時(shí)