物品快遞員配送路線優(yōu)化模型(完整版)
【正文】 解的距離矩陣，從而確定近似的最佳哈密爾頓圈，即最佳配送方案。問題一：配送員將前30號(hào)快件送到并返回，設(shè)計(jì)最佳的配送方案，使得路程最短。矩陣前兩列表示相互連接的配送點(diǎn)，第三列表示相鄰兩配送點(diǎn)之間邊的距離。判定一個(gè)加權(quán)圖是否存在哈密爾頓圈是一個(gè)NP問題，而它的完備加權(quán)圖(中每條邊的權(quán)等于之間的最短路徑的權(quán))中一定存在哈密爾頓圈。最佳H圈的近似解為：在中刪去邊和而加入邊和，形成新的H圈。由于考慮送貨員的最大載重與體積，送貨員必須分多次配送快件。圖四最終由程序解得三組最佳配送路線為：第一組： 5118718342543161710914162332353223172151解得路線總長52743m，第二組：512631241925414448463328302229222022151211131851解得路線總長47736m。而對(duì)于問題二與問題三，其最優(yōu)路線的求解均是建立在近似最優(yōu)哈密爾頓圈的基礎(chǔ)之上的。因此問題三存在配送點(diǎn)分組、以及每組求最佳配送方案這兩個(gè)問題。圖二最佳配送路線：5126211714162332353836384342494245403431273927312419131851解得路線總長為54709m。該過程需要采用二邊逐次修正法并且利用矩陣翻轉(zhuǎn)實(shí)現(xiàn)。 Floyd算法基本思想 直接在示意圖的帶權(quán)鄰接矩陣中，通過插入定點(diǎn)的方法構(gòu)造出n個(gè)矩陣,最后得到的矩陣為距離矩陣，同時(shí)求出插入點(diǎn)
公司管理相關(guān)推薦
鄂ICP備17016276號(hào)-1