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

1、1物流配送調(diào)度算法分析物流配送調(diào)度算法分析2022年年3月月15日日2Topicsn問(wèn)題描述問(wèn)題描述n算法輸入條件分析算法輸入條件分析n算法輸出分析算法輸出分析n算法指標(biāo)算法指標(biāo)n算法異常處理算法異常處理n算法框架算法框架n百度地圖接口調(diào)研百度地圖接口調(diào)研3問(wèn)題描述問(wèn)題描述n問(wèn)題背景：?jiǎn)栴}背景：n1. 城市中有固定的貨運(yùn)公交站點(diǎn)，貨運(yùn)公交運(yùn)城市中有固定的貨運(yùn)公交站點(diǎn)，貨運(yùn)公交運(yùn)行于各個(gè)站點(diǎn)間，并且可在各個(gè)站點(diǎn)進(jìn)行裝貨行于各個(gè)站點(diǎn)間，并且可在各個(gè)站點(diǎn)進(jìn)行裝貨和卸貨。和卸貨。n2. 通常在派發(fā)調(diào)度任務(wù)時(shí)，貨運(yùn)路線的信息是通常在派發(fā)調(diào)度任務(wù)時(shí)，貨運(yùn)路線的信息是已知的。貨運(yùn)車輛的數(shù)量和車輛起點(diǎn)（位置）

2、已知的。貨運(yùn)車輛的數(shù)量和車輛起點(diǎn)（位置）是已知的。但是車輛運(yùn)行時(shí)間和路線需要算法是已知的。但是車輛運(yùn)行時(shí)間和路線需要算法確定。確定。n算法確定的車輛起始和終點(diǎn)是否可以不同？已經(jīng)解算法確定的車輛起始和終點(diǎn)是否可以不同？已經(jīng)解決：起始點(diǎn)與線路相同，終點(diǎn)可以設(shè)置（決：起始點(diǎn)與線路相同，終點(diǎn)可以設(shè)置（1,線路起線路起始點(diǎn)，線路終點(diǎn)，可停車的站點(diǎn)）始點(diǎn)，線路終點(diǎn)，可停車的站點(diǎn)）4問(wèn)題描述問(wèn)題描述n3. 每個(gè)貨運(yùn)站點(diǎn)需要裝載或者卸載的貨物有重每個(gè)貨運(yùn)站點(diǎn)需要裝載或者卸載的貨物有重量、體積、數(shù)量、性質(zhì)等信息，同時(shí)指定了的量、體積、數(shù)量、性質(zhì)等信息，同時(shí)指定了的貨運(yùn)公交到達(dá)時(shí)間（貨運(yùn)公交車需要在此時(shí)間貨運(yùn)公交

3、到達(dá)時(shí)間（貨運(yùn)公交車需要在此時(shí)間之前到達(dá)）。之前到達(dá)）。n4. 貨物送到貨運(yùn)站點(diǎn)然后再送到指定的客戶。貨物送到貨運(yùn)站點(diǎn)然后再送到指定的客戶。n算法需要根據(jù)客戶地址確定該客戶訂單對(duì)應(yīng)的最近算法需要根據(jù)客戶地址確定該客戶訂單對(duì)應(yīng)的最近的貨運(yùn)站點(diǎn)的貨運(yùn)站點(diǎn)n5. 調(diào)度任務(wù)通常一天會(huì)派發(fā)兩次（上午，下午調(diào)度任務(wù)通常一天會(huì)派發(fā)兩次（上午，下午各一次）。各一次）。n算法運(yùn)行時(shí)間需要控制在算法運(yùn)行時(shí)間需要控制在2小時(shí)左右。（根據(jù)地圖小時(shí)左右。（根據(jù)地圖規(guī)模，站點(diǎn)數(shù)量等指標(biāo)來(lái)確定。）規(guī)模，站點(diǎn)數(shù)量等指標(biāo)來(lái)確定。）5問(wèn)題描述問(wèn)題描述n調(diào)度策略考慮的因素有：調(diào)度策略考慮的因素有：n（1）各個(gè)貨運(yùn)站點(diǎn)的發(fā)貨信息和收

4、貨信息、）各個(gè)貨運(yùn)站點(diǎn)的發(fā)貨信息和收貨信息、收發(fā)貨時(shí)間等。收發(fā)貨時(shí)間等。n（2）貨運(yùn)公交的信息；）貨運(yùn)公交的信息；n（3）道路信息；）道路信息； 6問(wèn)題描述問(wèn)題描述n調(diào)度策略滿足：調(diào)度策略滿足：n發(fā)出車量盡可能少，車輛裝載率高而空車率低，發(fā)出車量盡可能少，車輛裝載率高而空車率低，在滿足上述需求基礎(chǔ)上進(jìn)一步考慮車輛運(yùn)行里在滿足上述需求基礎(chǔ)上進(jìn)一步考慮車輛運(yùn)行里程的優(yōu)化。程的優(yōu)化。裝載率裝載率=實(shí)際裝載量實(shí)際裝載量/總裝載能力總裝載能力*100%空車率空車率=空車行走距離空車行走距離/配送的總距離配送的總距離*100%7算法輸入條件分析算法輸入條件分析1.線路基本信息線路基本信息 線線 路路基基本

5、本信信息息設(shè)設(shè)置置 預(yù)期出發(fā)時(shí)間、預(yù)期出發(fā)時(shí)間、 每條線路可以單獨(dú)設(shè)置，每條線路可以單獨(dú)設(shè)置，也可以設(shè)置一個(gè)值供所也可以設(shè)置一個(gè)值供所有線路使用有線路使用預(yù)期運(yùn)行時(shí)間、預(yù)期運(yùn)行時(shí)間、最長(zhǎng)運(yùn)行時(shí)間最長(zhǎng)運(yùn)行時(shí)間線路經(jīng)過(guò)的站點(diǎn)數(shù)量限制線路經(jīng)過(guò)的站點(diǎn)數(shù)量限制出發(fā)前后和貨運(yùn)站點(diǎn)交接時(shí)出發(fā)前后和貨運(yùn)站點(diǎn)交接時(shí)間間 每個(gè)站點(diǎn)可以有自己的每個(gè)站點(diǎn)可以有自己的交接時(shí)間也可以設(shè)置一交接時(shí)間也可以設(shè)置一個(gè)值供所有站點(diǎn)使用個(gè)值供所有站點(diǎn)使用線路與車輛關(guān)系線路與車輛關(guān)系每條線路可以有多輛車參與每條線路可以有多輛車參與運(yùn)輸任務(wù)，運(yùn)輸任務(wù)，車輛的終點(diǎn)車輛的終點(diǎn)可以是可以是(1)線路終點(diǎn)線路終點(diǎn)(2)線線路起點(diǎn)路起點(diǎn).(3)

6、 可停車的中間可停車的中間站點(diǎn)。站點(diǎn)。8算法輸入條件分析算法輸入條件分析2.車輛設(shè)置車輛設(shè)置2. 2. 車車輛輛設(shè)設(shè)置置車輛容積限制標(biāo)準(zhǔn)（體積、重量、兩者同時(shí)考慮、車輛容積限制標(biāo)準(zhǔn)（體積、重量、兩者同時(shí)考慮、其他單位）其他單位）每輛車輛需要單每輛車輛需要單獨(dú)設(shè)置限制標(biāo)準(zhǔn)獨(dú)設(shè)置限制標(biāo)準(zhǔn)提供車輛類型及每種類型的數(shù)量提供車輛類型及每種類型的數(shù)量每條線路的出發(fā)每條線路的出發(fā)點(diǎn)都應(yīng)該有此信點(diǎn)都應(yīng)該有此信息息車輛使用時(shí)的優(yōu)先順序或者車輛使用時(shí)的優(yōu)先順序或者系統(tǒng)自行比較車輛的組合方式。系統(tǒng)自行比較車輛的組合方式。默認(rèn)自有車輛優(yōu)先默認(rèn)自有車輛優(yōu)先每一輛車的起始站點(diǎn)、結(jié)束站點(diǎn)、發(fā)車時(shí)間每一輛車的起始站點(diǎn)、結(jié)束站

7、點(diǎn)、發(fā)車時(shí)間起始點(diǎn)已知，結(jié)束起始點(diǎn)已知，結(jié)束點(diǎn)，發(fā)車時(shí)間由點(diǎn)，發(fā)車時(shí)間由算法確定。算法確定。車牌（有些道路在特定日期限制單（雙）車牌）車牌（有些道路在特定日期限制單（雙）車牌）僅僅在路線規(guī)劃僅僅在路線規(guī)劃中使用中使用9算法輸入條件分析算法輸入條件分析 3.送貨策略設(shè)置（重點(diǎn)）送貨策略設(shè)置（重點(diǎn)）3.3.送貨策送貨策略設(shè)置略設(shè)置A.A.大宗貨物優(yōu)先：先送最大宗貨物，大宗貨物優(yōu)先：先送最大宗貨物，卸下后能減少后面路線的車行油卸下后能減少后面路線的車行油耗。耗。 默認(rèn)為默認(rèn)為D項(xiàng)。項(xiàng)。A,B,C項(xiàng)可以項(xiàng)可以與與D,E項(xiàng)組合項(xiàng)組合使用。使用。B.B.緊急訂單優(yōu)先：需要把緊急訂單緊急訂單優(yōu)先：需要把緊急

8、訂單先送掉；先送掉；C.C.最遠(yuǎn)客戶優(yōu)先（最近客戶優(yōu)先）最遠(yuǎn)客戶優(yōu)先（最近客戶優(yōu)先）D.D.行駛距離優(yōu)先；行駛距離優(yōu)先；E.E.運(yùn)行的時(shí)間優(yōu)先；運(yùn)行的時(shí)間優(yōu)先；10算法輸入條件分析算法輸入條件分析4.伙伴排序依據(jù)（具體含義？伙伴排序依據(jù)（具體含義？4.4.伙伙伴伴排排序序依依據(jù)據(jù)初始點(diǎn)初始點(diǎn)暫時(shí)不考慮）暫時(shí)不考慮）中心中心暫時(shí)不考慮）暫時(shí)不考慮）最近站點(diǎn)最近站點(diǎn)暫時(shí)不考慮）暫時(shí)不考慮）11算法輸入條件分析算法輸入條件分析5.契合時(shí)間窗的方式契合時(shí)間窗的方式5.5.契契合合時(shí)時(shí)間間窗窗的的方方式式線路出發(fā)時(shí)間是否允許調(diào)整、調(diào)整范圍線路出發(fā)時(shí)間是否允許調(diào)整、調(diào)整范圍（根據(jù)（根據(jù)車輛調(diào)整更合適，默認(rèn)

9、也可以應(yīng)用于該線車輛調(diào)整更合適，默認(rèn)也可以應(yīng)用于該線路中的所有車輛）路中的所有車輛）由線路中各個(gè)站由線路中各個(gè)站點(diǎn)的時(shí)間與車點(diǎn)的時(shí)間與車輛到達(dá)的時(shí)間輛到達(dá)的時(shí)間差來(lái)決定差來(lái)決定調(diào)整到達(dá)次序調(diào)整到達(dá)次序僅僅在線路內(nèi)部?jī)H僅在線路內(nèi)部調(diào)整調(diào)整調(diào)整等待時(shí)間調(diào)整等待時(shí)間( (不能為負(fù)數(shù)不能為負(fù)數(shù)) )僅僅在線路內(nèi)部?jī)H僅在線路內(nèi)部調(diào)整調(diào)整增加或者減少任務(wù)增加或者減少任務(wù)減少的任務(wù)將直減少的任務(wù)將直接刪除。增加接刪除。增加的任務(wù)如果出的任務(wù)如果出現(xiàn)不滿足的情現(xiàn)不滿足的情況將提醒。況將提醒。12算法輸入條件分析算法輸入條件分析6.數(shù)據(jù)信息數(shù)據(jù)信息n6.1 運(yùn)單信息運(yùn)單信息n貨物名稱、數(shù)量、體積、重量、發(fā)貨貨物

10、名稱、數(shù)量、體積、重量、發(fā)貨/收貨、收貨、常溫常溫/冷藏、貨物屬性、產(chǎn)生時(shí)間、可接收時(shí)冷藏、貨物屬性、產(chǎn)生時(shí)間、可接收時(shí)間、卸貨間、卸貨/裝貨耗時(shí)，起始站點(diǎn)、目標(biāo)站點(diǎn)。裝貨耗時(shí)，起始站點(diǎn)、目標(biāo)站點(diǎn)。n相同類型的運(yùn)輸任務(wù)可以同車；可接收時(shí)間為相同類型的運(yùn)輸任務(wù)可以同車；可接收時(shí)間為目標(biāo)站點(diǎn)可以接收訂單的時(shí)間范圍。目標(biāo)站點(diǎn)可以接收訂單的時(shí)間范圍。13算法輸入條件分析算法輸入條件分析6.數(shù)據(jù)信息數(shù)據(jù)信息n6.2道路信息道路信息n名稱、地址范圍、距離、單（雙）向、所屬區(qū)名稱、地址范圍、距離、單（雙）向、所屬區(qū)劃、交叉點(diǎn)。劃、交叉點(diǎn)。n道路級(jí)別及車速限制：州際、主干道路、次級(jí)道路級(jí)別及車速限制：州際、主

11、干道路、次級(jí)道路、地方道路和坡道，各級(jí)別道路對(duì)應(yīng)的車道路、地方道路和坡道，各級(jí)別道路對(duì)應(yīng)的車速及浮動(dòng)量。速及浮動(dòng)量。n道路限制道路限制:車型限制、單行道、高峰時(shí)間、高車型限制、單行道、高峰時(shí)間、高峰時(shí)間、高峰時(shí)車速、封路區(qū)域、封路時(shí)間、峰時(shí)間、高峰時(shí)車速、封路區(qū)域、封路時(shí)間、車牌單雙號(hào)等車牌單雙號(hào)等n此部分信息需要從此部分信息需要從GIS數(shù)據(jù)中拿到。數(shù)據(jù)中拿到。14算法輸入條件分析算法輸入條件分析6.數(shù)據(jù)信息數(shù)據(jù)信息n6.3 站點(diǎn)信息站點(diǎn)信息n貨運(yùn)節(jié)點(diǎn)地理信息貨運(yùn)節(jié)點(diǎn)地理信息 節(jié)點(diǎn)的經(jīng)緯度值。節(jié)點(diǎn)的經(jīng)緯度值。n節(jié)點(diǎn)屬性節(jié)點(diǎn)屬性 (取和送取和送)。(出發(fā)節(jié)點(diǎn)、返回節(jié)點(diǎn)、出發(fā)節(jié)點(diǎn)、返回節(jié)點(diǎn)、其他其

12、他)。n節(jié)點(diǎn)的車輛類型限制節(jié)點(diǎn)的車輛類型限制 m種車型。種車型。15算法輸出算法輸出1.1.路線路線站點(diǎn)（按到達(dá)順序排序）站點(diǎn)（按到達(dá)順序排序） 序號(hào)，站點(diǎn)描述、序號(hào)，站點(diǎn)描述、站點(diǎn)地址、立方、時(shí)間段表（希望時(shí)間站點(diǎn)地址、立方、時(shí)間段表（希望時(shí)間與預(yù)計(jì)到達(dá)時(shí)間）與預(yù)計(jì)到達(dá)時(shí)間） 。輸出界面上可以。輸出界面上可以進(jìn)行手動(dòng)微調(diào)。進(jìn)行手動(dòng)微調(diào)。手動(dòng)微調(diào)是僅限于手動(dòng)微調(diào)是僅限于線路內(nèi)部調(diào)整線路內(nèi)部調(diào)整嗎？如果有節(jié)嗎？如果有節(jié)點(diǎn)刪除，刪除點(diǎn)刪除，刪除節(jié)點(diǎn)怎么處理？節(jié)點(diǎn)怎么處理？2.2.地圖顯示地圖顯示a.a.地圖上顯示站點(diǎn)的運(yùn)輸順序地圖上顯示站點(diǎn)的運(yùn)輸順序;b.;b.車輛行駛車輛行駛路徑信息，包括各個(gè)車

13、輛經(jīng)過(guò)的道路、路徑信息，包括各個(gè)車輛經(jīng)過(guò)的道路、車輛在停靠站點(diǎn)以及各個(gè)站點(diǎn)?？康臅r(shí)車輛在停靠站點(diǎn)以及各個(gè)站點(diǎn)?？康臅r(shí)間。上述路徑信息可最終向用戶顯示出間。上述路徑信息可最終向用戶顯示出時(shí)段圖、配送路線、線路播放時(shí)段圖、配送路線、線路播放地圖顯示需要地理地圖顯示需要地理系完成，并需系完成，并需要確定好接口；要確定好接口；車輛運(yùn)行路線車輛運(yùn)行路線的存儲(chǔ)及顯示的存儲(chǔ)及顯示需要與需要與GISGIS系統(tǒng)系統(tǒng)溝通溝通3.3.調(diào)度統(tǒng)計(jì)調(diào)度統(tǒng)計(jì)信息信息調(diào)配車輛數(shù)目，總里程數(shù)、理論上的總費(fèi)用、調(diào)配車輛數(shù)目，總里程數(shù)、理論上的總費(fèi)用、每輛行駛里程數(shù)、理論上的成本及費(fèi)用每輛行駛里程數(shù)、理論上的成本及費(fèi)用（油耗等）（

14、油耗等）16算法指標(biāo)算法指標(biāo)1.1.裝載率，空車裝載率，空車率，無(wú)貢獻(xiàn)時(shí)率，無(wú)貢獻(xiàn)時(shí)長(zhǎng)長(zhǎng)裝載率裝載率=85%=85%；空車率；空車率=20%=20%；無(wú)貢獻(xiàn)時(shí)長(zhǎng)無(wú)貢獻(xiàn)時(shí)長(zhǎng)=30%=30%；等待時(shí)長(zhǎng)；等待時(shí)長(zhǎng)/ /總時(shí)長(zhǎng)總時(shí)長(zhǎng)2.2.規(guī)模規(guī)模支撐業(yè)務(wù)量為支撐業(yè)務(wù)量為500500個(gè)節(jié)點(diǎn)、個(gè)節(jié)點(diǎn)、100000100000票托運(yùn)單、票托運(yùn)單、15001500輛輛車；運(yùn)行時(shí)間不大于車；運(yùn)行時(shí)間不大于2 2小時(shí)。小時(shí)。17異常情況異常情況1.1.運(yùn)單量運(yùn)單量運(yùn)單量超出車輛運(yùn)力。運(yùn)單量超出車輛運(yùn)力。運(yùn)輸時(shí)間不滿足，運(yùn)輸時(shí)間不滿足，當(dāng)選用最合適當(dāng)選用最合適的車盡最快速的車盡最快速度運(yùn)輸，到達(dá)度運(yùn)輸，到達(dá)時(shí)間不

15、滿足時(shí)時(shí)間不滿足時(shí)報(bào)警；報(bào)警；2.2.運(yùn)單時(shí)間運(yùn)單時(shí)間運(yùn)輸車輛不能滿足運(yùn)單時(shí)間要求。運(yùn)輸車輛不能滿足運(yùn)單時(shí)間要求。運(yùn)單體積過(guò)大，運(yùn)單體積過(guò)大，運(yùn)單體積超出運(yùn)單體積超出可用車輛最大可用車輛最大容量時(shí)報(bào)警；容量時(shí)報(bào)警；3.3.單個(gè)運(yùn)單單個(gè)運(yùn)單運(yùn)輸車輛不能滿足運(yùn)單重量或者體積；運(yùn)輸車輛不能滿足運(yùn)單重量或者體積；提醒然后處理。提醒然后處理。運(yùn)單超重。當(dāng)運(yùn)運(yùn)單超重。當(dāng)運(yùn)單重量超出整單重量超出整個(gè)車輛載重限個(gè)車輛載重限制時(shí)報(bào)警。制時(shí)報(bào)警。18算法框架算法框架n算法框架包括主要三個(gè)部分：算法框架包括主要三個(gè)部分：n1.根據(jù)系統(tǒng)的運(yùn)輸線路設(shè)置和約束條件獲取該根據(jù)系統(tǒng)的運(yùn)輸線路設(shè)置和約束條件獲取該運(yùn)輸線路的伙伴

16、站點(diǎn)。運(yùn)輸線路的伙伴站點(diǎn)。n2. 根據(jù)伙伴站點(diǎn)的數(shù)量和約束條件確定運(yùn)輸?shù)母鶕?jù)伙伴站點(diǎn)的數(shù)量和約束條件確定運(yùn)輸?shù)能囕v。車輛。n3.根據(jù)車輛的運(yùn)單和約束條件對(duì)運(yùn)輸路徑調(diào)整。根據(jù)車輛的運(yùn)單和約束條件對(duì)運(yùn)輸路徑調(diào)整。19算法框架算法框架n1.根據(jù)系統(tǒng)的運(yùn)輸線路設(shè)置和約束條件獲根據(jù)系統(tǒng)的運(yùn)輸線路設(shè)置和約束條件獲取該運(yùn)輸線路的伙伴站點(diǎn)。取該運(yùn)輸線路的伙伴站點(diǎn)。n計(jì)算每條線路從起點(diǎn)到終點(diǎn)的最短路徑。計(jì)算每條線路從起點(diǎn)到終點(diǎn)的最短路徑。n用插入法比較加入一個(gè)新的運(yùn)單之后，最短路用插入法比較加入一個(gè)新的運(yùn)單之后，最短路徑的變化，選擇最優(yōu)的站點(diǎn)進(jìn)入到路線中。徑的變化，選擇最優(yōu)的站點(diǎn)進(jìn)入到路線中。n運(yùn)行一段時(shí)間之后

17、可以將插入法和歷史數(shù)據(jù)結(jié)合考運(yùn)行一段時(shí)間之后可以將插入法和歷史數(shù)據(jù)結(jié)合考慮。從而獲取更加合適的伙伴集合。慮。從而獲取更加合適的伙伴集合。n重復(fù)上述過(guò)程得到各個(gè)線路對(duì)應(yīng)的運(yùn)單集合。重復(fù)上述過(guò)程得到各個(gè)線路對(duì)應(yīng)的運(yùn)單集合。20算法框架算法框架n2.根據(jù)伙伴站點(diǎn)的數(shù)量和約束條件確定運(yùn)根據(jù)伙伴站點(diǎn)的數(shù)量和約束條件確定運(yùn)輸?shù)能囕v。輸?shù)能囕v。n對(duì)伙伴站點(diǎn)按照到達(dá)時(shí)間的先后排序，按照順對(duì)伙伴站點(diǎn)按照到達(dá)時(shí)間的先后排序，按照順序安排運(yùn)單，主要考慮的因素有：序安排運(yùn)單，主要考慮的因素有：n運(yùn)單是否滿足時(shí)間需要；運(yùn)單是否滿足時(shí)間需要；n運(yùn)單的距離因素；運(yùn)單的距離因素；n車輛的裝載和空車；車輛的裝載和空車；n需要定義一個(gè)約束函數(shù)來(lái)計(jì)算。需要定義一個(gè)約束函數(shù)來(lái)計(jì)算。21算法框架算法框架n3.根據(jù)車輛的運(yùn)單和約束條件對(duì)運(yùn)輸路徑根據(jù)車輛的運(yùn)單和約束條件對(duì)運(yùn)輸路徑調(diào)整。調(diào)整。n在各個(gè)車輛的運(yùn)輸任務(wù)確定之后根據(jù)運(yùn)單的情在各個(gè)車輛的運(yùn)輸任務(wù)確定之后根據(jù)運(yùn)單的情況來(lái)確定最短路徑。此時(shí)問(wèn)題簡(jiǎn)化為旅行商問(wèn)況來(lái)確定最短路徑。此時(shí)問(wèn)題簡(jiǎn)化為旅行商問(wèn)題（題（TSP）。）。n考慮用啟發(fā)式算法，增加歷史數(shù)據(jù)的參考。考慮用啟發(fā)式算法，增加歷史數(shù)據(jù)的參考。n也可以對(duì)比各種經(jīng)典算法，選擇合適的。也可以對(duì)比各種經(jīng)典算法，選擇合適的。