番茄路徑優(yōu)化系統(tǒng)介紹
大家好,最近消失了一陣子。因?yàn)檫@兩周一直在折騰一款產(chǎn)品。事情是這樣的,此前搞算法一直是和命令行打交道基本上,搞得心煩,然后前陣子上頭條偶然看到一些前端框架做的系統(tǒng),感覺還挺好看的,也蠻有趣的。于是就躍躍欲試想嘗試下新的東西,加上此前不是做了很多算法嘛,有了一定的基礎(chǔ)積累,于是想著把算法和UI結(jié)合起來,搞款能用的算法產(chǎn)品試試。
1、問題背景
整個(gè)項(xiàng)目還是基于VRP的一個(gè)背景,處理的問題在涵蓋經(jīng)典VRPTW的基礎(chǔ)上,還包括了處理以下約束的能力:
- 多時(shí)間窗(一般由于客戶營(yíng)業(yè)休息時(shí)間等安排,會(huì)允許出現(xiàn)多個(gè)配送時(shí)間窗)
- 多車型(涵蓋冷鏈車型和常規(guī)車型,大型車輛和小型車輛等,能夠進(jìn)行混合配送)
- 交通管制約束(有些地方不允許大型的車輛進(jìn)入,只能安排小型車進(jìn)行配送)
- 時(shí)間窗為硬時(shí)間窗(早到等待,不允許晚到)
- 客戶需求多樣化(常規(guī)的貨物,冷鏈配送要求的貨物)
- 等等
2、算法性能
系統(tǒng)的核心算法引擎基于啟發(fā)式算法開發(fā),具有比較優(yōu)秀的性能。不過口說無憑,將我們的算法和cplex進(jìn)行對(duì)比,首先是小規(guī)模算例上的對(duì)比(規(guī)定了CPLEX求解時(shí)間上限為1小時(shí)):
可以看到,相比較cplex而言,我們的算法有以下特點(diǎn):
小規(guī)模算例對(duì)比
- 質(zhì)量更高:算例(1-7)我們的算法均取得了與CPLEX同樣的最優(yōu)解,在算例(8-11)上我們的算法取得了比CPLEX在1小時(shí)內(nèi)求得的可行解更優(yōu)的解(表中值越低越好)
- 時(shí)間更快:除了算例1時(shí)間略高于CPLEX外,其余算例時(shí)間均比CPLEX低。且CPLEX的求解時(shí)間隨著問題規(guī)模增加呈指數(shù)增長(zhǎng)。當(dāng)規(guī)模變大時(shí),問題的求解時(shí)間急劇增加,在現(xiàn)實(shí)中很難應(yīng)用。而我們的算法求解時(shí)間隨問題規(guī)模增長(zhǎng)呈線性增長(zhǎng),能夠在較快的時(shí)間內(nèi)求解較大規(guī)模的問題(分鐘級(jí))。
在大規(guī)模算例下(客戶節(jié)點(diǎn)60-200時(shí)),我們的算法求解結(jié)果與CPLEX在1小時(shí)內(nèi)求得的可行解進(jìn)行對(duì)比:
大規(guī)模算例下對(duì)比
-相比商業(yè)求解器CPLEX在1小時(shí)內(nèi)求得的可行解,我們的算法得出的解成本更低。
-如圖所示(時(shí)間越少越好),可以看出,在客戶規(guī)模為60-200的算例下,我們算法的求解時(shí)間遠(yuǎn)低于CPLEX的求解時(shí)間。
同時(shí)為了彌補(bǔ)啟發(fā)式算法在求解質(zhì)量上的不足,我在算法中應(yīng)用了一種全新的“鄰域搜索多樣化”技術(shù)
發(fā)表評(píng)論
請(qǐng)輸入評(píng)論內(nèi)容...
請(qǐng)輸入評(píng)論/評(píng)論長(zhǎng)度6~500個(gè)字
最新活動(dòng)更多
-
即日-10.29立即報(bào)名>> 2024德州儀器嵌入式技術(shù)創(chuàng)新發(fā)展研討會(huì)
-
10月31日立即下載>> 【限時(shí)免費(fèi)下載】TE暖通空調(diào)系統(tǒng)高效可靠的組件解決方案
-
即日-11.13立即報(bào)名>>> 【在線會(huì)議】多物理場(chǎng)仿真助跑新能源汽車
-
11月14日立即報(bào)名>> 2024工程師系列—工業(yè)電子技術(shù)在線會(huì)議
-
12月19日立即報(bào)名>> 【線下會(huì)議】OFweek 2024(第九屆)物聯(lián)網(wǎng)產(chǎn)業(yè)大會(huì)
-
即日-12.26火熱報(bào)名中>> OFweek2024中國(guó)智造CIO在線峰會(huì)
推薦專題
- 1 Intel宣布40年來最重大轉(zhuǎn)型:年底前裁員15000人、拋掉2/3房產(chǎn)
- 2 因美封殺TikTok,字節(jié)股價(jià)骨折!估值僅Meta1/5
- 3 宏山激光重磅發(fā)布行業(yè)解決方案,助力智能制造產(chǎn)業(yè)新飛躍
- 4 國(guó)產(chǎn)AI芯片公司破產(chǎn)!白菜價(jià)拍賣
- 5 具身智能火了,但規(guī)模落地還需時(shí)間
- 6 國(guó)產(chǎn)英偉達(dá)們,抓緊沖刺A股
- 7 三次錯(cuò)失風(fēng)口!OpenAI前員工殺回AI編程賽道,老東家捧金相助
- 8 英特爾賦能智慧醫(yī)療,共創(chuàng)數(shù)字化未來
- 9 英偉達(dá)的麻煩在后頭?
- 10 將“網(wǎng)紅”變成“商品”,AI“爆改”實(shí)力拉滿
- 高級(jí)軟件工程師 廣東省/深圳市
- 自動(dòng)化高級(jí)工程師 廣東省/深圳市
- 光器件研發(fā)工程師 福建省/福州市
- 銷售總監(jiān)(光器件) 北京市/海淀區(qū)
- 激光器高級(jí)銷售經(jīng)理 上海市/虹口區(qū)
- 光器件物理工程師 北京市/海淀區(qū)
- 激光研發(fā)工程師 北京市/昌平區(qū)
- 技術(shù)專家 廣東省/江門市
- 封裝工程師 北京市/海淀區(qū)
- 結(jié)構(gòu)工程師 廣東省/深圳市