【文章內(nèi)容簡(jiǎn)介】 路運(yùn)輸模型 TSP 模型求解。通過(guò) lingo 程序（附錄 2）解決路線的選擇。得到 第一條路線優(yōu)化后的路線為 013450。 用以上方法可以得到其它的路線 （ 1） 0 1 3 4 5 0 （ 2） 0 2 13 7 6 0 （ 3） 0 10 12 8 9 0 （ 4） 0 16 17 20 14 15 23 0 （ 5） 0 11 19 2 1 22 0 （ 6） 0 27 26 0 （ 7） 0 18 24 25 0 （ 8） 0 29 30 28 0 則 站點(diǎn)數(shù) ， 所用時(shí)間，總載重（ kg），總路程（ km）如下： 線路編號(hào) 送貨路線 路程（公里） 負(fù)重（千克） 站點(diǎn)數(shù) 時(shí)間（小時(shí)） 線路 1 013450 32 24 4 線路 2 0267130 43 4 線路 3 09812100 42 4 線路 4 01617201415230 90 6 線路 5 0112221190 72 3 線路 6 027260 76 22 2 線路 7 01824250 68 3 線路 8 02928300 96 3 總計(jì) 522 30 優(yōu)化前后 的路程和時(shí)間的比較如下 ： 10 012345線路 1 線路 2 線路 3 線路 4 線路 5 線路 6 線路 7 線路 8時(shí)間比較優(yōu)化前優(yōu)化后 由表共有八條路線，其中 線路 1和線路 6累計(jì)時(shí)間不足 6小時(shí)，可選派一名快遞員分兩次運(yùn)送。同理，線路 2 和 3 也可以由一名快遞員運(yùn)送。所以整個(gè)過(guò)程只需要 6名快遞員。 快遞員 1:線路 1，線路 6； 快遞員 2:線路 2，線路 3； 快遞員 3:線路 4 ； 快遞員 4:線路 5； 快遞員 5:線路 7； 快遞員 6: 線路 8； 方案 二：每一個(gè)行程的第一個(gè)送貨點(diǎn)是距離總部最遠(yuǎn)的未服務(wù)的送貨點(diǎn)。 分析方法和方案一相似，只不過(guò)是從離原點(diǎn)的最遠(yuǎn)端開(kāi)始 優(yōu)化 前 線路編號(hào) 送貨路線 路程（公里） 負(fù)重 站點(diǎn)數(shù) 時(shí)間（小 時(shí) ） 線路 1 030292823150 96 5 線路 2 0262780 75 3 線路 3 02425190 68 25 3 線路 4 0181720160 64 4 線路 5 02122111090 52 25 5 線路 6 01413120 52 3 線路 7 07430 34 3 線路 8 056210 34 4 總計(jì) 475 30 同方 案 一，進(jìn)行優(yōu)化 。 11 優(yōu)化后的 路線： 線路編號(hào) 送貨路線 路程（公里） 負(fù)重 站點(diǎn)數(shù) 時(shí)間（小時(shí)） 線路 1 029283023150 91 5 線路 2 0826270 76 3 線路 3 01924250 68 25 3 線路 4 0161718200 58 4 線路 5 09112122100 54 25 5 線路 6 01213140 52 3 線路 7 03740 32 3 線路 8 016520 30 4 總計(jì) 461 30 優(yōu)化前后比較： 同樣共有八條路線， 根據(jù)所經(jīng)歷的時(shí)間進(jìn)行劃分，確定運(yùn)送人數(shù)。在工作時(shí)間小于 6 小時(shí)的前提下，最終只 需要五名快遞員， 第三條線路和第八條線路由一人完成 第四條線路和第七條線路由一人完成，第五條線路和第六條線路由一人完成 。 快遞員 1：線路 1； 12 快遞員 2：線路 2； 快遞員 3：線路 3， 線路 8 快遞員 4：線路 4，線路 7 快遞員 5：線路 5，線路 6； 通過(guò)以上兩種方法的比較，考慮時(shí)間和路程因素我們可以得出： 方案 路程（ km） 時(shí)間（ h） 方案一 522 方案二 461 方法二更優(yōu)其最優(yōu)路程為 461km，所需的總的時(shí)間為 。 問(wèn)題 2 模型建立 在業(yè)務(wù)員 送貨 次數(shù)為 N的情況下，本問(wèn)題可以轉(zhuǎn)化為利用 01整數(shù)規(guī)劃對(duì)總的費(fèi)用實(shí)施滿足條件的最小化；再次，對(duì)所建立的單目標(biāo)模型利用 Lingo 軟件求解，并分析數(shù)據(jù)，列出每條路線上的時(shí)間耗費(fèi)表；最后，根據(jù)上述表中的數(shù)據(jù)，利用最佳匹配的原理，對(duì)業(yè)務(wù)員的人數(shù)安排進(jìn)行重新調(diào)配，得到總行運(yùn)路程最小情況下，快遞公司所需業(yè)務(wù)員人數(shù)最少的策略，此時(shí)即為一種合理的方案。 類似于問(wèn)題一的研究方法，可以將本問(wèn)題的方法分析如下： 問(wèn)題中由于業(yè)務(wù)員所得的費(fèi)用是最主要的，業(yè)務(wù)員安排、路線選擇都是為了總費(fèi)用的最小化提供條件，所以應(yīng)首先考慮路費(fèi)，之后再考慮 業(yè)務(wù)員的安排。為了使總能夠費(fèi)用最少，總的思路是先送貨給離快遞公司最近切塊間最重的送貨點(diǎn)，以此類推，在保證時(shí)間、載重量有限的前提下，沿途把快遞送完，最終讓業(yè)務(wù)員最遠(yuǎn)點(diǎn)空載返回。根據(jù)這一思路，全部路線業(yè)務(wù)員的重載費(fèi)用可表示為： 30= 3 ( )j1S a j jxyj ???不 空 從上式可以看出，業(yè)務(wù)員的重載費(fèi)用是恒定的，又由于總費(fèi)用為重載與空載費(fèi)用之和，所以總費(fèi)用的確定就可以轉(zhuǎn)化為滿足一定條件下的各路線的最遠(yuǎn)點(diǎn)的選擇問(wèn)題。某路線業(yè)務(wù)員經(jīng)過(guò)的路徑選擇應(yīng)遵循以下原則： （ 1） 近者優(yōu)先原則。某業(yè)務(wù)員最近起始送貨點(diǎn) 的選擇直接關(guān)系到費(fèi)用的多少，所以該業(yè)務(wù)員在沿途往送貨終點(diǎn)站中應(yīng)盡量把較近點(diǎn)的快件送完，不讓下一條路線再把較近點(diǎn)作為起始送貨站。 （ 2） 不走冤枉路原則（即只能向上或者向右走）。 一方面，離原點(diǎn)（快遞公司）較遠(yuǎn)的送貨點(diǎn)坐標(biāo)應(yīng)分別大于離原點(diǎn)較近送貨點(diǎn)的坐標(biāo)，在各個(gè)坐標(biāo)上均不走回頭路，即按圖（ a）中的①②路線前進(jìn)，而不按③路線前進(jìn)： 13 另一方面，由于在路途相等的條件下，重載費(fèi)用要比空載費(fèi)用大得多，因此，盡量讓業(yè)務(wù)員空載行走 （ 3） 坐標(biāo)貼近原則。在同一條路線中，離原點(diǎn)較近送貨點(diǎn)的坐標(biāo)僅次于較遠(yuǎn)點(diǎn)的坐標(biāo)。四是，路線 較少原則。路線多，一方面，相對(duì)最遠(yuǎn)點(diǎn)的選擇多，跑的空路多，費(fèi)用就多；另一方面，過(guò)分地強(qiáng)調(diào)短暫效益，出動(dòng)路線多，會(huì)引起業(yè)務(wù)員的反感，不利于以后的人員控制。 根據(jù)上述分析及基本假設(shè)，業(yè)務(wù)員送貨的費(fèi)用可以表示如下： 業(yè)務(wù)員攜帶快件時(shí)公司應(yīng)付費(fèi)用為 ： 30= 3 ( )j1S a j jxyj ???不 空 由于業(yè)務(wù)員不攜帶快件時(shí)的速度是 30千米 /小時(shí)，酬金 2 元 /千米，因此，業(yè)務(wù)員不攜帶快件時(shí)，公司應(yīng)付費(fèi)用為： 30= 3 ( )j11NS a j jxyji ??? ??空 根據(jù)題意，業(yè)務(wù)員攜帶與不攜帶快件時(shí)，按第 i條路線派送快 件所需時(shí)間分別為 p ( ) 1 20jjxyij