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

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

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

倉庫差的串聯(lián)倉庫更好的串聯(lián)車輛將停留點(diǎn)串起來的示意圖

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

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

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

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

倉庫

倉庫

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

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

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

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

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

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

23579864195.4018171314101115121680.30M1與M3距離36線路總長度（英里）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)輸——最短路徑求解方法

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

對最短路徑問題的描述如下：

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

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

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

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

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

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

多點(diǎn)間運(yùn)輸——運(yùn)輸算法有m個已知的供應(yīng)點(diǎn)A={a1，a2，…，am}，有n個已知的需求點(diǎn)B={b1，b2，…，bn}，它們之間有一系列代表距離或成本的權(quán)重值cij連接起來。數(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ù)滿足a1a2amb1bncij供應(yīng)點(diǎn)需求點(diǎn)……多點(diǎn)間運(yùn)輸調(diào)配問題的求解方法單純形法表上作業(yè)法（運(yùn)輸算法）運(yùn)用相關(guān)軟件TRANLP(LOGWARE)求法相對精確，但計(jì)算冗長，一般需借助計(jì)算機(jī)進(jìn)行計(jì)算。將運(yùn)輸問題用表格的形式來描述，求解過程方便直觀，計(jì)算量不大，可用手工直接完成，適合于簡單問題的求解。［例］一制造商有三個工廠分別是1、2、3，且同時有三家供應(yīng)商A、B、C。工廠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)商到每個工廠單位質(zhì)量的運(yùn)輸成本如下圖所示。工廠1

需求量=600工廠2

需求量=500工廠3

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

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

500供應(yīng)商B