大家好，最近消失了一陣子。因?yàn)檫@兩周一直在折騰一款產(chǎn)品。事情是這樣的，此前搞算法一直是和命令行打交道基本上，搞得心煩，然后前陣子上頭條偶然看到一些前端框架做的系統(tǒng)，感覺還挺好看的，也蠻有趣的。于是就躍躍欲試想嘗試下新的東西，加上此前不是做了很多算法嘛，有了一定的基礎(chǔ)積累，于是想著把算法和UI結(jié)合起來，搞款能用的算法產(chǎn)品試試。
1、問題背景
整個(gè)項(xiàng)目還是基于VRP的一個(gè)背景，處理的問題在涵蓋經(jīng)典VRPTW的基礎(chǔ)上，還包括了處理以下約束的能力：
－ 多時(shí)間窗（一般由于客戶營業(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)行對比，首先是小規(guī)模算例上的對比（規(guī)定了CPLEX求解時(shí)間上限為1小時(shí)）：
可以看到，相比較cplex而言，我們的算法有以下特點(diǎn)：
小規(guī)模算例對比
－ 質(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ù)增長。當(dāng)規(guī)模變大時(shí)，問題的求解時(shí)間急劇增加，在現(xiàn)實(shí)中很難應(yīng)用。而我們的算法求解時(shí)間隨問題規(guī)模增長呈線性增長，能夠在較快的時(shí)間內(nèi)求解較大規(guī)模的問題（分鐘級）。
在大規(guī)模算例下（客戶節(jié)點(diǎn)60－200時(shí)），我們的算法求解結(jié)果與CPLEX在1小時(shí)內(nèi)求得的可行解進(jìn)行對比：
大規(guī)模算例下對比
－相比商業(yè)求解器CPLEX在1小時(shí)內(nèi)求得的可行解，我們的算法得出的解成本更低。
－如圖所示（時(shí)間越少越好），可以看出，在客戶規(guī)模為60－200的算例下，我們算法的求解時(shí)間遠(yuǎn)低于CPLEX的求解時(shí)間。
同時(shí)為了彌補(bǔ)啟發(fā)式算法在求解質(zhì)量上的不足，我在算法中應(yīng)用了一種全新的“鄰域搜索多樣化”技術(shù)
123下一頁>（免責(zé)聲明：本網(wǎng)站內(nèi)容主要來自原創(chuàng)、合作伙伴供稿和第三方自媒體作者投稿，凡在本網(wǎng)站出現(xiàn)的信息，均僅供參考。本網(wǎng)站將盡力確保所提供信息的準(zhǔn)確性及可靠性，但不保證有關(guān)資料的準(zhǔn)確性及可靠性，讀者在使用前請進(jìn)一步核實(shí)，并對任何自主決定的行為負(fù)責(zé)。本網(wǎng)站對有關(guān)資料所引致的錯(cuò)誤、不確或遺漏，概不負(fù)任何法律責(zé)任。
任何單位或個(gè)人認(rèn)為本網(wǎng)站中的網(wǎng)頁或鏈接內(nèi)容可能涉嫌侵犯其知識產(chǎn)權(quán)或存在不實(shí)內(nèi)容時(shí)，應(yīng)及時(shí)向本網(wǎng)站提出書面權(quán)利通知或不實(shí)情況說明，并提供身份證明、權(quán)屬證明及詳細(xì)侵權(quán)或不實(shí)情況證明。本網(wǎng)站在收到上述法律文件后，將會(huì)依法盡快聯(lián)系相關(guān)文章源頭核實(shí)，溝通刪除相關(guān)內(nèi)容或斷開相關(guān)鏈接。 ）
