配送問(wèn)題模型

1、配送問(wèn)題模型一、 摘要本文通過(guò)給出運(yùn)輸公司為十個(gè)客戶配送貨物，從第i個(gè)客戶到第j個(gè)客戶的路線距離（單位公里），求出最短的路徑，即最短路徑法。針對(duì)問(wèn)題一、二，要求出第i個(gè)客戶到第j個(gè)客戶的最短路徑。這個(gè)問(wèn)題可以使用圖論的方法解決。我們分別用1,2 ，10十個(gè)點(diǎn)表示從第i個(gè)客戶到第j個(gè)客戶的位置，再把所有的點(diǎn)對(duì)都用邊連接起來(lái)，邊（i，j）上賦以數(shù)值w,它表示從第i個(gè)客戶到第j個(gè)客戶的距離。因此使用Dijkstra(迪杰斯特拉)算法求出這個(gè)問(wèn)題的最優(yōu)策略，得到最短距離。Dijkstra(迪杰斯特拉)算法是典型的單源最短路徑算法，用于計(jì)算一個(gè)節(jié)點(diǎn)到其他所有節(jié)點(diǎn)的最短路徑。主要特點(diǎn)是以起始點(diǎn)為中心向外層

2、層擴(kuò)展，直到擴(kuò)展到終點(diǎn)為止。針對(duì)問(wèn)題三，我們首先直接利用問(wèn)題二得一輛車的最優(yōu)回路，以貨車容量為限定條件，建立相應(yīng)的規(guī)劃模型并設(shè)計(jì)一個(gè)簡(jiǎn)單的尋路算法，最終可為公司確定合理的一號(hào)運(yùn)輸方案:兩輛車全程總和為295公里；然后建立線性規(guī)劃模型得出二號(hào)運(yùn)輸方案：兩輛車全程總和為290公里；最后再進(jìn)一步優(yōu)化所建的線性規(guī)劃模型，為運(yùn)輸公司獻(xiàn)上一個(gè)最優(yōu)的決策即三號(hào)運(yùn)輸方案：車號(hào)行車路線線路的長(zhǎng)度該車負(fù)責(zé)的客戶一號(hào)車135公里2，3，4，5，8二號(hào)車145公里6，7，9，10兩輛車全程總和為280公里。針對(duì)問(wèn)題四，我們首先用Dijkstra算法確定提貨點(diǎn)到每個(gè)客戶點(diǎn)間的最短路線，然后結(jié)合一些限定條件建立一個(gè)目標(biāo)模

3、型，設(shè)計(jì)一個(gè)較好的解決方案進(jìn)行求解可得到一種很理想的運(yùn)輸方案：車號(hào)行車路線車號(hào)行車路線一號(hào)車三號(hào)車二號(hào)車四號(hào)車該方案得到運(yùn)輸總費(fèi)用是645元。關(guān)鍵詞：Dijkstra(迪杰斯特拉)算法 最短路徑 二、 問(wèn)題重述某運(yùn)輸公司為10個(gè)客戶配送貨物，假定提貨點(diǎn)就在客戶1所在的位置，從第i個(gè)客戶到第j個(gè)客戶的路線距離（單位公里）用下面矩陣中的位置上的數(shù)表示（其中表示兩個(gè)客戶之間無(wú)直接的路線到達(dá)）。圖（一）分別解決以下問(wèn)題：1、運(yùn)送員在給第二個(gè)客戶卸貨完成的時(shí)候，臨時(shí)接到新的調(diào)度通知，讓他先給客戶10送貨，已知送給客戶10的貨已在運(yùn)送員的車上，請(qǐng)幫運(yùn)送員設(shè)計(jì)一個(gè)到客戶10的盡可能短的行使路線（假定上述矩陣

4、中給出了所有可能的路線選擇）。2、現(xiàn)運(yùn)輸公司派了一輛大的貨車為這10個(gè)客戶配送貨物，假定這輛貨車一次能裝滿10個(gè)客戶所需要的全部貨物，請(qǐng)問(wèn)貨車從提貨點(diǎn)出發(fā)給10個(gè)客戶配送完貨物后再回到提貨點(diǎn)所行使的盡可能短的行使路線？對(duì)所設(shè)計(jì)的算法進(jìn)行分析。3、現(xiàn)因資源緊張，運(yùn)輸公司沒(méi)有大貨車可以使用，改用兩輛小的貨車配送貨物。每輛小貨車的容量為50個(gè)單位，每個(gè)客戶所需要的貨物量分別為8，13，6，9，7，15，10，5，12，9個(gè)單位，請(qǐng)問(wèn)兩輛小貨車應(yīng)該分別給那幾個(gè)客戶配送貨物以及行使怎樣的路線使它們從提貨點(diǎn)出發(fā)最后回到提貨點(diǎn)所行使的距離之和盡可能短？對(duì)所設(shè)計(jì)的算法進(jìn)行分析。4、如果改用更小容量的車，每車容

5、量為25個(gè)單位，但用車數(shù)量不限，每個(gè)客戶所需要的貨物量同第3問(wèn)，并假設(shè)每出一輛車的出車費(fèi)為100元，運(yùn)貨的價(jià)格為1元/公里（不考慮空車返回的費(fèi)用），請(qǐng)問(wèn)如何安排車輛才能使得運(yùn)輸公司運(yùn)貨的總費(fèi)用最??？ 四、 問(wèn)題分析 對(duì)于問(wèn)題一，它是在運(yùn)送員給第二個(gè)客戶卸貨完成的時(shí)候，才臨時(shí)接到新的調(diào)度通知，讓他先給客戶10送貨，并且送給客戶10的貨已在運(yùn)送員的車上，為了幫運(yùn)送員設(shè)計(jì)一個(gè)到客戶10的盡可能短的行駛路線。所以，可以考慮用圖論的方法來(lái)解決。在這里，我們分別用1,2，10十個(gè)點(diǎn)表示這十個(gè)客戶所在的位置，并根據(jù)矩陣中的信息將其有路線的點(diǎn)連接起來(lái)，邊（i,j）(i,j=1,2,，10)上賦予數(shù)值w它表示從

6、第i個(gè)客戶到第j個(gè)客戶的總路程。因此我們可以畫出運(yùn)送員的路線選擇圖，再運(yùn)用Dijkstra算法求出這個(gè)問(wèn)題的最短的行駛路線。 對(duì)于問(wèn)題二，它所要求的是貨車從提貨點(diǎn)出發(fā)給10個(gè)客戶配送完貨物后再回到提貨點(diǎn)所行駛的盡可能短的行駛路線。因此可以類似地運(yùn)用問(wèn)題一的解決方法來(lái)進(jìn)行求解。方案一： 方案二： 根據(jù)方案一，盡可能短的路線為：；L=25+10+25+30+15+20+10+20+20+50=225根據(jù)方案二，盡可能短的路線為：；L=25+10+25+30+15+25+10+20+20+50=230因此，方案一的路徑小于方案二，故采用方案二。對(duì)于問(wèn)題三：對(duì)于問(wèn)題四： 四、模型假設(shè)（1）假定圖（一）

7、矩陣中給出了所有可能的路線選擇；（2）w它表示從第i個(gè)客戶到第j個(gè)客戶的總路程(3) 表示兩個(gè)客戶之間無(wú)直接的路線到達(dá)；(4) 針對(duì)問(wèn)題四，不考慮空車返回的費(fèi)用；五、模型的建立與求解問(wèn)題一求解： 1 2 3 4 5 6 7 8 9 10 50 30 15 45 60 25 30 10 2402550103020503060604050303555606520353003555551045 圖（二）根據(jù)Dijkstra算法求出這個(gè)問(wèn)題的最優(yōu)策略，過(guò)程如下：?jiǎn)栴}二求解：按照Dijkstra算法求出這個(gè)問(wèn)題的最優(yōu)策略，過(guò)程如下：所以，盡可能短的路線為：；L=25+10+25+30+15+20+10+20+20+50=225問(wèn)題四求解：由分析知可以建立問(wèn)題的模型（目標(biāo)函數(shù)）：依解決方案，能得出運(yùn)輸公司所派出的