物流運(yùn)輸線(xiàn)路規(guī)劃

運(yùn)輸與配送的線(xiàn)路規(guī)劃

合理的運(yùn)行路線(xiàn)和時(shí)間安排原則點(diǎn)點(diǎn)間運(yùn)輸——最短路徑求解方法多點(diǎn)間運(yùn)輸——運(yùn)輸算法案例1伊萬(wàn)斯維爾地方學(xué)區(qū)為小學(xué)生提供校車(chē)服務(wù)。如圖所示，現(xiàn)有一輛校車(chē)被分派到該地區(qū)。已知每年學(xué)生的新名冊(cè)，接送學(xué)生的停車(chē)點(diǎn)位置在地圖上標(biāo)出。對(duì)各站點(diǎn)進(jìn)行排序以確定校車(chē)每次行駛所需的時(shí)間和距離。利用你最佳的感知技巧設(shè)計(jì)滿(mǎn)足下列條件的最短路徑：經(jīng)過(guò)所有停車(chē)點(diǎn)。孩子們可以在街道的任何一邊上下車(chē)。住在臨近街區(qū)的孩子可以在拐彎處上下車(chē)。不允許轉(zhuǎn)U形彎。校車(chē)有足夠空間，可以接送路上所有的學(xué)生。借助尺子計(jì)算校車(chē)行駛的總距離。校車(chē)路線(xiàn)制定練習(xí)123456789101112141315161718192021習(xí)題4答案1.將相互接近的停留點(diǎn)的貨物裝在一輛車(chē)上運(yùn)送2.將集聚在一起的停留點(diǎn)安排同一天送貨3.運(yùn)行路線(xiàn)從離倉(cāng)庫(kù)最遠(yuǎn)的停留點(diǎn)開(kāi)始。4.一輛運(yùn)貨車(chē)順次途經(jīng)各停留點(diǎn)的路線(xiàn)要成淚滴狀。5.盡可能使用最大的車(chē)輛進(jìn)行運(yùn)送。6.取貨、送貨應(yīng)該混合安排，不應(yīng)該在完成全部送貨任務(wù)之后再取貨。7.對(duì)偏離集聚停留點(diǎn)路線(xiàn)遠(yuǎn)的單獨(dú)的停留點(diǎn)可應(yīng)用另一個(gè)送貨方案。8.應(yīng)當(dāng)避免停留點(diǎn)工作時(shí)間太短的約束。一.合理的運(yùn)行路線(xiàn)和時(shí)間安排原則1.將相互接近的停留點(diǎn)的貨物裝在一輛車(chē)上運(yùn)送

倉(cāng)庫(kù)差的串聯(lián)倉(cāng)庫(kù)更好的串聯(lián)車(chē)輛將停留點(diǎn)串起來(lái)的示意圖

DD倉(cāng)庫(kù)停留點(diǎn)倉(cāng)庫(kù)2.將集聚在一起的停留點(diǎn)安排同一天送貨

不合理的—路線(xiàn)交叉劃分方式較合理的—線(xiàn)路劃分方式一周各天停留點(diǎn)群的劃分FFFFFFFTTTTTTTD倉(cāng)庫(kù)FFFFFTTTFTFTTTD倉(cāng)庫(kù)(a)(b)停留點(diǎn)3.運(yùn)行路線(xiàn)從離倉(cāng)庫(kù)最遠(yuǎn)的停留點(diǎn)開(kāi)始。首先應(yīng)劃分出離倉(cāng)庫(kù)最遠(yuǎn)的停留點(diǎn)集聚區(qū)。選定距該核心停留點(diǎn)最近的一些停留點(diǎn)形成停留點(diǎn)集聚區(qū)，分派載貨能力能滿(mǎn)足該停留點(diǎn)集聚區(qū)需要的卡車(chē)。從還沒(méi)有分派車(chē)輛的其他停留點(diǎn)中找出距倉(cāng)庫(kù)最遠(yuǎn)的站點(diǎn)，分派另一車(chē)輛。4.一輛運(yùn)貨車(chē)順次途經(jīng)各停留點(diǎn)的路線(xiàn)要成淚滴狀。根據(jù)經(jīng)驗(yàn)，當(dāng)運(yùn)行路線(xiàn)不發(fā)生交叉時(shí)，經(jīng)過(guò)各停留點(diǎn)的次序是合理的，同時(shí)，應(yīng)盡量使運(yùn)行路線(xiàn)形成淚滴狀。運(yùn)輸路線(xiàn)示意圖

不好的線(xiàn)路規(guī)劃—線(xiàn)路交叉

好的線(xiàn)路規(guī)劃—線(xiàn)路不交叉

倉(cāng)庫(kù)

倉(cāng)庫(kù)

［例］安休瑟—布喜公司(Anheuser—BuschCompany)利用售貨員通過(guò)流動(dòng)卡車(chē)銷(xiāo)售啤酒和其它飲料，卡車(chē)由當(dāng)?shù)亟?jīng)銷(xiāo)人員所有。公司售貨員同當(dāng)?shù)亟?jīng)銷(xiāo)人員一樣都是收取傭金，因而都不希望每天向各客戶(hù)提供服務(wù)時(shí)花費(fèi)不必要的時(shí)間，行走多余的路程。他們將圖釘固定在地圖上，以確定某推銷(xiāo)員現(xiàn)有客戶(hù)的位置。圖中所舉的是一個(gè)20個(gè)客戶(hù)的例子，客戶(hù)點(diǎn)的信息已經(jīng)被轉(zhuǎn)換到網(wǎng)格地圖上，圖中的坐標(biāo)與距離相關(guān)。我們要找出的是，卡車(chē)從倉(cāng)庫(kù)出發(fā)，經(jīng)過(guò)所有的客戶(hù)點(diǎn)，再回到倉(cāng)庫(kù)，這個(gè)運(yùn)行過(guò)程中距離最短的路徑。建議的路徑

用軟件ROUTE的計(jì)算結(jié)果。整個(gè)行程的總成本為37.59距離單位。

比例尺：1＝5英里珠寶推銷(xiāo)員問(wèn)題中客戶(hù)(X)和汽車(chē)旅館(Y)的位置習(xí)題丹·帕普(DanPupp)是個(gè)珠寶推銷(xiāo)員，他需要走訪(fǎng)中西部的店鋪。圖中列出了他負(fù)責(zé)的某個(gè)銷(xiāo)售區(qū)域。他的工作方式是在走訪(fǎng)的前一天晚上來(lái)到這個(gè)地區(qū)，住在當(dāng)?shù)氐钠?chē)旅館里，花兩天時(shí)間走訪(fǎng)這個(gè)地區(qū)，隨后在第三天早上離開(kāi)。由于是自己付費(fèi)，他希望總成本能夠最小。第一天要走訪(fǎng)第1至第9位客戶(hù)，第二天走訪(fǎng)其余的客戶(hù)。他有兩個(gè)方案可供比較。方案1：三晚都住在汽車(chē)旅館M2中，住宿費(fèi)是每晚49.00美元。方案2：前兩晚都住在汽車(chē)旅館M1中，走訪(fǎng)客戶(hù)l至9，住宿費(fèi)為每晚40.00美元。隨后，搬到汽車(chē)旅館M3住一晚，走訪(fǎng)客戶(hù)10至18，住宿費(fèi)是每晚45.00美元。在走訪(fǎng)客戶(hù)l至9后，推銷(xiāo)員回到M1，在此過(guò)夜。隨后，搬到M3，過(guò)夜并于次日早晨離開(kāi)。M1和M3相距36英里。不管丹在這個(gè)地區(qū)的什么地方，旅行成本都是0.30美元／英里。哪個(gè)方案對(duì)丹最好?答案方案1

路線(xiàn)停留點(diǎn)順序距離

86412357995.4010131417181612151186.46線(xiàn)路總長(zhǎng)度（英里）181.86方案1的總成本為：住宿費(fèi)：49×3＝147美元旅行費(fèi)用：181.86×0.30＝54.56美元總成本：201.56美元答案方案2

路線(xiàn)停留點(diǎn)順序距離

23579864195.4018171314101115121680.30M1與M3距離36線(xiàn)路總長(zhǎng)度（英里）211.70方案1的總成本為：住宿費(fèi)：40+40+45＝125美元旅行費(fèi)用：211.70×0.30＝63.51美元總成本：188.51美元采用第二種方案最好二.點(diǎn)點(diǎn)間運(yùn)輸——最短路徑求解方法

（配送貨物由一個(gè)配送中心直達(dá)某客戶(hù)）最短路問(wèn)題的含義最短路問(wèn)題的基本原型求解最短路問(wèn)題的算法1.最短路問(wèn)題的含義連通圖的最短路問(wèn)題指求兩個(gè)頂點(diǎn)間長(zhǎng)度最短的路徑。

對(duì)最短路徑問(wèn)題的描述如下：

假設(shè)有一n個(gè)節(jié)點(diǎn)和m條弧的連通圖G(Vn，Em)，并且圖中的每條弧（i，j）都有一個(gè)長(zhǎng)度cij（或者費(fèi)用cij），則最短路徑問(wèn)題為：在連通圖G中找到一條從節(jié)點(diǎn)1到節(jié)點(diǎn)n距離最短（或費(fèi)用最低）的路徑。

用數(shù)學(xué)方法表達(dá)是：

存在連通圖G(Vn，Em)，且長(zhǎng)度矩陣C={cij│1≤i≤n，1≤j≤n│}

目標(biāo)函數(shù)：sabcdeft98774564565742.最短路問(wèn)題的基本原型對(duì)工程實(shí)際的研究和抽象，在最短路徑問(wèn)題中有3種基本原型：連通圖G(Vn，Em)中，從指定起始點(diǎn)到指定目的點(diǎn)之間的最短路徑。連通圖G(Vn，Em)中，從指定起始點(diǎn)到其余所有節(jié)點(diǎn)之間的最短路徑。連通圖G(Vn，Em)中，所有任意兩點(diǎn)之間的最短路徑。sabcdeft98774564565743.求解最短路問(wèn)題的算法Dijkstra算法

標(biāo)號(hào)設(shè)定法、標(biāo)號(hào)修正法逐次逼近法Floyd算法sabcdeft9877456456574574810916sabcdeft9877456456574指起始點(diǎn)或目的點(diǎn)不唯一的運(yùn)輸調(diào)配問(wèn)題。多點(diǎn)間運(yùn)輸中最常見(jiàn)的問(wèn)題是產(chǎn)銷(xiāo)平衡問(wèn)題。

設(shè)計(jì)的總供應(yīng)能力和總需求是一樣，但是由不同的路徑進(jìn)行配送時(shí)，會(huì)導(dǎo)致最終的總運(yùn)輸成本不一樣，此類(lèi)問(wèn)題的目標(biāo)就是尋找最低的總運(yùn)輸成本。三.

多點(diǎn)間運(yùn)輸——運(yùn)輸算法有m個(gè)已知的供應(yīng)點(diǎn)A={a1，a2，…，am}，有n個(gè)已知的需求點(diǎn)B={b1，b2，…，bn}，它們之間有一系列代表距離或成本的權(quán)重值cij連接起來(lái)。數(shù)學(xué)模型：條件變量：A：供應(yīng)點(diǎn)的供應(yīng)能力矩陣B：需求點(diǎn)的需求矩陣C：運(yùn)輸距離或成本矩陣決策變量：xij=從ai到bj的發(fā)送量a1a2amb1bncij供應(yīng)點(diǎn)需求點(diǎn)……目標(biāo)函數(shù)滿(mǎn)足a1a2amb1bncij供應(yīng)點(diǎn)需求點(diǎn)……多點(diǎn)間運(yùn)輸調(diào)配問(wèn)題的求解方法單純形法表上作業(yè)法（運(yùn)輸算法）運(yùn)用相關(guān)軟件TRANLP(LOGWARE)求法相對(duì)精確，但計(jì)算冗長(zhǎng)，一般需借助計(jì)算機(jī)進(jìn)行計(jì)算。將運(yùn)輸問(wèn)題用表格的形式來(lái)描述，求解過(guò)程方便直觀(guān)，計(jì)算量不大，可用手工直接完成，適合于簡(jiǎn)單問(wèn)題的求解。［例］一制造商有三個(gè)工廠(chǎng)分別是1、2、3，且同時(shí)有三家供應(yīng)商A、B、C。工廠(chǎng)1、2、3的需求量分別為600、500、300（重量單位），而A、B、C的供應(yīng)量分別也有限制。A最大的供應(yīng)量為400，B最大的供應(yīng)量為700，C最大的供應(yīng)量為500。每一供應(yīng)商到每個(gè)工廠(chǎng)單位質(zhì)量的運(yùn)輸成本如下圖所示。工廠(chǎng)1

需求量=600工廠(chǎng)2

需求量=500工廠(chǎng)3

需求量=300供應(yīng)商A供應(yīng)量

400供應(yīng)商C供應(yīng)量

500供應(yīng)商B