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

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

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

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

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

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

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

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

倉庫

倉庫

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

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

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

路線停留點順序距離

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

路線停留點順序距離

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

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

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

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

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

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

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

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

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

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

需求量=600工廠2

需求量=500工廠3

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

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

500供應(yīng)商B