番茄路徑優(yōu)化系統(tǒng)介紹

代碼黑科技的分享區(qū)

大家好，最近消失了一陣子。因?yàn)檫@兩周一直在折騰一款產(chǎn)品。事情是這樣的，此前搞算法一直是和命令行打交道基本上，搞得心煩，然后前陣子上頭條偶然看到一些前端框架做的系統(tǒng)，感覺還挺好看的，也蠻有趣的。于是就躍躍欲試想嘗試下新的東西，加上此前不是做了很多算法嘛，有了一定的基礎(chǔ)積累，于是想著把算法和UI結(jié)合起來，搞款能用的算法產(chǎn)品試試。

1

問題背景

2

算法性能

系統(tǒng)的核心算法引擎基于啟發(fā)式算法開發(fā)，具有比較優(yōu)秀的性能。不過口說無憑，將我們的算法和cplex進(jìn)行對比，首先是小規(guī)模算例上的對比（規(guī)定了CPLEX求解時(shí)間上限為1小時(shí)）：

通過對搜索過程中的目標(biāo)值增加懲罰從而避免陷入局部最優(yōu)，以擴(kuò)大搜索過程的多樣性達(dá)到尋找更優(yōu)解的目的。

從圖上可以看出，加了“鄰域搜索多樣化”技術(shù)后的算法效果明顯比未加之前的要好，求解得到的解成本均有降低。

3

系統(tǒng)介紹

好了上面介紹了一下核心算法，這里來介紹下系統(tǒng)的UI界面。整個(gè)系統(tǒng)的UI采用的技術(shù)棧是springboot+vue前后端分離開發(fā)的模式，數(shù)據(jù)庫采用的是mysql。由于我對前后端這些完全沒有學(xué)過，這兩周開發(fā)的過程中都是邊學(xué)邊做的。其中踩過的坑和無數(shù)吐血的經(jīng)歷等以后有時(shí)間再介紹了。唉~

系統(tǒng)的主界面如下：

初次使用需要到任務(wù)管理中添加一個(gè)任務(wù)，填寫任務(wù)名和任務(wù)相關(guān)描述，上傳算例文件保存任務(wù)后，便可以開始對任務(wù)進(jìn)行相應(yīng)的操作：

系統(tǒng)后端會對算例文件進(jìn)行一個(gè)校驗(yàn)的操作，如果是瞎上傳的不符合格式的文件，會被撤掉。

添加完任務(wù)后，可以在參數(shù)設(shè)置模塊對算法的參數(shù)進(jìn)行相關(guān)的設(shè)置，右邊是具體參數(shù)的詳細(xì)說明：

然后就可以回到主頁面對剛剛添加的任務(wù)進(jìn)行一個(gè)求解了。當(dāng)在任務(wù)操作中選擇一個(gè)任務(wù)，左下角的地圖便會將算例中的客戶節(jié)點(diǎn)在地圖上標(biāo)注出來：

隨后便可以點(diǎn)擊啟動算法，進(jìn)行求解，該過程是動態(tài)演示的過程，會隨著后端算法的求解不斷更新頁面上的信息，包括當(dāng)前進(jìn)度，當(dāng)前最優(yōu)解的詳情，算法收斂曲線等，該過程也可以隨時(shí)點(diǎn)擊停止按鈕終止算法：

求解完成后，左下角的地圖會將求得的路徑在地圖上給逐一展示出來，同時(shí)也能看到整個(gè)過程的算法收斂曲線，包括當(dāng)前解（可能不可行）和最優(yōu)解曲線（必須為可行解，不然不會畫出來），還有最優(yōu)解的路徑具體詳情：

同時(shí)，求解的結(jié)果也可以進(jìn)一步保存到后臺的數(shù)據(jù)庫中，相關(guān)詳情可以在結(jié)果查看中進(jìn)行管理：

點(diǎn)擊某個(gè)任務(wù)的詳情后，便可以將該任務(wù)的求解記錄詳情給展示出來：

當(dāng)然，小編還為此制作了演示視頻（人家說天不怕地不怕就怕咱廣東人說普通話……）：

關(guān)于該系統(tǒng)，有感興趣的小伙伴可以聯(lián)系我進(jìn)一步細(xì)聊。不過源碼暫時(shí)不會公開的。

推薦閱讀：

干貨 | 想學(xué)習(xí)優(yōu)化算法，不知從何學(xué)起？

干貨 | 運(yùn)籌學(xué)從何學(xué)起？如何快速入門運(yùn)籌學(xué)算法？

干貨 | 學(xué)習(xí)算法，你需要掌握這些編程基礎(chǔ)（包含JAVA和C++）

干貨 | 算法學(xué)習(xí)必備訣竅：算法可視化解密