參考設(shè)計(1)(含文本格式、任務(wù)書、指導(dǎo)書、裝訂順序).doc

課課 程程 設(shè)設(shè) 計計 課程名稱課程名稱 交通運(yùn)輸組織學(xué)交通運(yùn)輸組織學(xué) 設(shè)計題目設(shè)計題目 學(xué)生姓名學(xué)生姓名 學(xué)學(xué) 號號 班班 級級 院系名稱院系名稱 交通運(yùn)輸工程學(xué)院交通運(yùn)輸工程學(xué)院 指導(dǎo)老師指導(dǎo)老師 注 指導(dǎo)老師欄 一班填 周騫 柳武生 盛玉奎 李瓊星 注 指導(dǎo)老師欄 一班填 周騫 柳武生 盛玉奎 李瓊星 二班填 周騫 柳武生 劉鵬飛 向慧 二班填 周騫 柳武生 劉鵬飛 向慧 2015 年年 1 月月 交通運(yùn)輸組織學(xué)交通運(yùn)輸組織學(xué) 課課 程程 設(shè)設(shè) 計計 課程名稱課程名稱 交通運(yùn)輸組織學(xué)交通運(yùn)輸組織學(xué) 設(shè)計題目設(shè)計題目 學(xué)生姓名學(xué)生姓名 學(xué)學(xué) 號號 班班 級級 院系名稱院系名稱 交通運(yùn)輸工程學(xué)院交通運(yùn)輸工程學(xué)院 指導(dǎo)老師指導(dǎo)老師 長沙理工大學(xué)課程設(shè)計任務(wù)書 交通運(yùn)輸工程 學(xué)院 交通運(yùn)輸 專業(yè) 2011 級 班 課程名稱 交通運(yùn)輸組織學(xué) 題 目 學(xué)生姓名 學(xué)號 同組設(shè)計者 無 一 已知技術(shù)參數(shù)和設(shè)計要求一 已知技術(shù)參數(shù)和設(shè)計要求 1 已知技術(shù)參數(shù)與參考資料 已知技術(shù)參數(shù)與參考資料 交通運(yùn)輸部客貨運(yùn)組織與管理相關(guān)標(biāo)準(zhǔn)與規(guī)范 孟祥茹 運(yùn)輸組織學(xué) M 北京大學(xué)出版社 2014 年 李維斌 公路運(yùn)輸組織學(xué) M 人民交通出版社 2008 年 崔書堂 朱艷茹 交通運(yùn)輸組織學(xué) M 東南大學(xué)出版社 2008 年 戴彤焱 運(yùn)輸組織學(xué) M 機(jī)械工業(yè)出版社 2008 年 2 設(shè)計要求 設(shè)計要求 本課程設(shè)計是針對學(xué)生學(xué)習(xí)和運(yùn)用專業(yè)知識的綜合考核和檢查 使學(xué)生接受工程類基 本訓(xùn)練的重要環(huán)節(jié) 是 交通運(yùn)輸組織學(xué) 專業(yè)課程學(xué)習(xí)的必修內(nèi)容之一 本課程設(shè)計的 特點(diǎn)是 內(nèi)容所涉及的知識面較一般習(xí)題廣 有較強(qiáng)的系統(tǒng)性和綜合性 在運(yùn)算 繪圖 編寫設(shè)計文本方面有較高的要求 本課程實際應(yīng)針對交通運(yùn)算組織學(xué)課程涉及的相關(guān)理論與方法 結(jié)合具體實踐背景 解決實際問題 要求 所涉及方法 模型與理論知識與本課程相關(guān) 有具體的實踐背景 課程實際要求完整 系統(tǒng) 從提出問題 解決問題與結(jié)論三個方面開展 思路清 晰 條理清楚 主要內(nèi)容 道路運(yùn)輸市場調(diào)查分析與預(yù)測 道路客運(yùn)班次計劃編制 客運(yùn)站場交通組 織設(shè)計 公交營運(yùn)計劃編制 貨運(yùn)線路優(yōu)化 貨運(yùn)車輛優(yōu)化調(diào)度設(shè)計 旅客或貨物運(yùn)輸計 劃編制 運(yùn)輸站場規(guī)劃 車船配載優(yōu)化 多式聯(lián)運(yùn)組織 甩掛運(yùn)輸 集裝箱運(yùn)輸?shù)认冗M(jìn)運(yùn) 輸方式組織設(shè)計 危險物品及大件物品運(yùn)輸組織設(shè)計及其他與運(yùn)輸組織有關(guān)的設(shè)計等 二 課程設(shè)計應(yīng)完成的任務(wù)二 課程設(shè)計應(yīng)完成的任務(wù) 課程設(shè)計應(yīng)結(jié)合課程內(nèi)容 獨(dú)立解決運(yùn)輸組織實際問題 本設(shè)計應(yīng)完成以下幾個方 面的任務(wù) 第一 闡述設(shè)計背景和內(nèi)容以及本設(shè)計的思路 完成本設(shè)計的實際背景和相關(guān)實際數(shù) 據(jù)分析等 第二 完成設(shè)計所需要的方法及理論的闡述 第三 結(jié)合上述理論與方法 應(yīng)用于實際背景 解決實際應(yīng)用問題 第四 對設(shè)計結(jié)論總結(jié)分析 三 工作計劃三 工作計劃 本次課程設(shè)計安排時間為三周 2014 年 12 月 15 日至 2015 年 1 月 3 日 具體工作 計劃如下 1 2014 年 12 月 15 日 16 日 項目背景資料的收集 數(shù)據(jù)與整理 2 2014 年 12 月 17 日 20 日 完成課程設(shè)計背景與基礎(chǔ)資料的分析 完成課程設(shè)計 大綱 3 2014 年 12 月 21 日 22 日 進(jìn)行相關(guān)理論與模型分析 4 2014 年 12 月 23 日 31 日 進(jìn)行具體運(yùn)輸組織方案設(shè)計 完成設(shè)計圖表與文本 5 2015 年 1 月 1 日 2015 年 1 月 3 日 完成修改工作 四 課程設(shè)計完成提交文檔要求四 課程設(shè)計完成提交文檔要求 按照以下順序裝訂成冊 1 封面 2 扉頁 3 任務(wù)書 4 指導(dǎo)書 5 目錄 6 正文 7 附錄 表格或圖紙 8 成績評定表 指導(dǎo)老師 同意按照任務(wù)書要求開展設(shè)計 教研室意見 同意按照任務(wù)書要求開展設(shè)計 教研室主任 時間 注 1 此任務(wù)書由指導(dǎo)老師填寫 如果不夠 可以加頁 1 此任務(wù)書最遲必須在課程設(shè)計開始前一周下達(dá)給學(xué)生 交通運(yùn)輸組織學(xué)課程設(shè)計指導(dǎo)書交通運(yùn)輸組織學(xué)課程設(shè)計指導(dǎo)書 一 課程設(shè)計目的與要求 1 課程設(shè)計目的 課程設(shè)計目的 課程設(shè)計是對學(xué)生學(xué)習(xí)和運(yùn)用專業(yè)知識的綜合考核和檢查 是學(xué)生接受工程師基本訓(xùn) 練的重要環(huán)節(jié) 是整個課程學(xué)習(xí)的重要組成部分 本課程設(shè)計的目的是 使學(xué)生掌握交通 運(yùn)輸組織相關(guān)的理論與知識 并能理論聯(lián)系實際 進(jìn)行具體的運(yùn)輸組織案例分析設(shè)計 為 畢業(yè)后從事相關(guān)工作提供理論與實踐支持 同時 通過本課程設(shè)計 使學(xué)生掌握資料查找 以及繪圖 文本編輯等方法 為畢業(yè)設(shè)計 論文 順利完成打下基礎(chǔ) 2 課程設(shè)計要求 課程設(shè)計要求 要求學(xué)生根據(jù)課程涉及的相關(guān)內(nèi)容與方法 結(jié)合實際背景 系統(tǒng)解決實際問題 從背 景分析 提出問題 解決問題 主要結(jié)論等幾個方面開展 要求課程設(shè)計具有系統(tǒng)性 完 整性 與課程相關(guān)性并具有一定的深度 二 課程設(shè)計的依據(jù)與資料來源 課程設(shè)計的依據(jù) 交通運(yùn)輸部客貨運(yùn)組織與管理相關(guān)標(biāo)準(zhǔn)與規(guī)范 孟祥茹 運(yùn)輸組織學(xué) M 北京大學(xué)出版社 2014 年 李維斌 公路運(yùn)輸組織學(xué) M 人民交通出版社 2008 年 崔書堂 朱艷茹 交通運(yùn)輸組織學(xué) M 東南大學(xué)出版社 2008 年 戴彤焱 運(yùn)輸組織學(xué) M 機(jī)械工業(yè)出版社 2008 年 資料來源 指導(dǎo)教師提供相關(guān)資料 實際調(diào)研收集資料 相關(guān)設(shè)計書籍 網(wǎng)絡(luò)資料收 集 三 課程設(shè)計學(xué)生應(yīng)完成的內(nèi)容 根據(jù) 交通運(yùn)輸組織學(xué) 課程設(shè)計要求及線路優(yōu)化設(shè)計內(nèi)容 學(xué)生應(yīng)按照以下幾個方 面內(nèi)容開展設(shè)計 第一 設(shè)計背景和以及本設(shè)計的思路 完成本設(shè)計的實際背景和相關(guān)實際數(shù)據(jù)說明等 第二 完成設(shè)計所需要的方法及理論的闡述 第三 結(jié)合上述理論與方法 應(yīng)用于實際背景 解決實際存在的問題 第四 對設(shè)計結(jié)論的總結(jié)分析 四 課程設(shè)計要求及其它 1 時間安排 三周 2014 年 12 月 15 日至 2015 年 1 月 3 日 實際操作中 可提前 進(jìn)行相關(guān)資料的收集與大綱的完成 2 要求獨(dú)立完成 一人一題 每人提交 1 份打印的設(shè)計成果 A4 及電子文檔 3 格式要求 按照要求的順序依次裝訂成冊 膠裝封面 文檔具體格式參考格式模板 4 紀(jì)律要求 集中在固定教室嚴(yán)格考勤 按時作息 一般不允許請假 如遇特殊情況 需要填寫請假條報院領(lǐng)導(dǎo)批準(zhǔn) 否則按照每天曠課 8 節(jié)處理 另請假或曠課時數(shù)累計達(dá)全 部設(shè)計時間的 1 3 以上 該課程設(shè)計按照零分計 運(yùn)輸與物流工程系 2014 年 12 月 目目 錄錄 第一章第一章 概述概述 1 1 1 設(shè)計背景和內(nèi)容 1 1 2 問題的提出 2 1 2 1 配送作業(yè)問題的提出 2 1 2 2 配送路線優(yōu)化問題的提出 2 1 3 本設(shè)計所做的工作及基本結(jié)構(gòu) 3 1 3 1 設(shè)計的主要工作 3 1 3 2 設(shè)計的基本結(jié)構(gòu) 4 第二章第二章 貨運(yùn)中心配送路線優(yōu)化的研究現(xiàn)狀貨運(yùn)中心配送路線優(yōu)化的研究現(xiàn)狀 5 2 1 配送路線優(yōu)化的意義 5 2 2 貨運(yùn)中心路線優(yōu)化的方法 5 2 2 1 配送路線優(yōu)化問題的簡化 6 2 2 2 配送路線的計劃方法 7 2 2 3 配送路線優(yōu)化分類 8 2 3 貨運(yùn)中心路線優(yōu)化原則 10 第三章第三章 南城平安 深圳 貨運(yùn)公司配送線路現(xiàn)狀南城平安 深圳 貨運(yùn)公司配送線路現(xiàn)狀 11 3 1 公司業(yè)務(wù)狀況 11 3 1 1 公司簡介 11 3 1 2 公司的業(yè)務(wù)狀況 11 3 2 公司的配送路線 12 3 2 1 國內(nèi)主要城市配送方式 12 3 2 2 省內(nèi)主要配送方式 12 3 3 存在的主要問題及分析 13 第四章第四章 貨運(yùn)中心配送路線的優(yōu)化設(shè)計貨運(yùn)中心配送路線的優(yōu)化設(shè)計 16 4 1 優(yōu)化思路 16 4 2 市內(nèi)配送優(yōu)化 16 4 2 1 主要狀況 16 4 2 2 南城平安 深圳 貨運(yùn)公司配送路線優(yōu)化模型 17 第五章第五章 南城平安 深圳 貨運(yùn)公司線路優(yōu)化模型的求解南城平安 深圳 貨運(yùn)公司線路優(yōu)化模型的求解 19 5 1 節(jié)約法的基本思想與步驟 19 5 1 1 節(jié)約法的基本思想 19 5 1 2 模型的求解步驟 20 5 2 簡單節(jié)約法的求解 21 5 2 1 求解過程分析 21 5 2 2 節(jié)約法應(yīng)注意的事項 6 24 5 2 3 節(jié)約法的優(yōu)缺點(diǎn)及改進(jìn)建議 25 5 3 用改進(jìn)的節(jié)約法制定配送計劃 25 5 3 1 用 a b 尺度制定配送計劃 26 5 3 2 用 a b 尺度制定配送計劃 28 5 4 配送計劃軟件的實際運(yùn)用 29 5 4 1 計劃軟件的運(yùn)用 29 5 4 2 配送和流通中心的關(guān)系 30 5 5 本章小結(jié) 31 第六章第六章 總結(jié)總結(jié) 32 6 1 設(shè)計主要成果 32 6 2 需要進(jìn)一步闡述的問題 32 6 3 對南城平安 貨運(yùn) 公司的幾點(diǎn)建議 33 參參 考考 文文 獻(xiàn)獻(xiàn) 35 交通運(yùn)輸組織學(xué) 課程設(shè)計 1 第一章第一章 概述概述 1 1 設(shè)計背景和內(nèi)容 在經(jīng)濟(jì)日益全球化的今天 現(xiàn)代物流作為 第三個利潤源 正受到日益廣 泛的重視 并面臨著前所未的有發(fā)展機(jī)遇 我國物流業(yè)面對的機(jī)遇與挑戰(zhàn)也愈 來愈明顯 特別是加入 WTO 以后 我國融入世界經(jīng)濟(jì)一體化的進(jìn)程逐漸加快 物流業(yè)已成為市場經(jīng)濟(jì)中一個競爭激烈的行業(yè) 我國的物流市場被國外物流業(yè) 普遍看好 認(rèn)為這是一塊尚未很好開拓的領(lǐng)域 可以大有作為 因此紛紛來我 國開辦物流企業(yè) 這也刺激了我國物流業(yè)的發(fā)展 在市場經(jīng)濟(jì)下 如何贏得更多的利潤是每一個企業(yè)追求的目標(biāo) 現(xiàn)在很多 企業(yè)已經(jīng)開始把目光投向了被經(jīng)濟(jì)學(xué)家稱為繼勞動力 自然資源 之后的 第 三和利潤源泉 物流管理 2 在這種形式下 物流配送也得到了相應(yīng)的發(fā) 展 配送的基本含義是送貨的意思 在美國的英語原詞是 Delivery 強(qiáng)調(diào)的是 將貨物送達(dá) 在現(xiàn)代的物流配送中 為實現(xiàn)利潤最大化 就得想方設(shè)法使送貨 行為優(yōu)化 于是出現(xiàn)了配送中心的車輛合理調(diào)度 倉儲管理的優(yōu)化 配送路線 的規(guī)劃選擇等問題 配送是一種綜合的物流形式 幾乎包括了所有物流功能要素 是物流的一 個縮影或在某小范圍中物流全部活動的體現(xiàn) 配送中心是進(jìn)行配送活動最主要 的硬件設(shè)施 其作業(yè)流程具體表現(xiàn)為配送中心進(jìn)行生產(chǎn)的實際過程 配送流程 的合理 則配送的生產(chǎn)效率和效益就高 反之就低 因此對配送的研究具有很 高的實際意義和價值 要搞好配送物流 就必須合理化配送中心的作業(yè)流程 從而最大化的利用 配送中心的資源 對于配送中心的一系列環(huán)節(jié) 應(yīng)該首先著重研究哪些環(huán)節(jié)并 如何去解決這些問題 是本文所要提出和解決的問題 在目前 配送中心的基本作業(yè)流程包括進(jìn)貨 儲存 揀貨 配貨 送貨等 環(huán)節(jié) 每個環(huán)節(jié)都與貨物的搬運(yùn)是分不開的 而其中把貨物由配送中心搬運(yùn)至 各顧客點(diǎn) 就引發(fā)了一個如何使路線達(dá)到優(yōu)化的問題 這是本文研究的重點(diǎn) 對于路線優(yōu)化的研究 可以提高企業(yè)的運(yùn)作能力 有助于企業(yè)獲取更多的利潤 和選擇更合理的配送經(jīng)營決策 交通運(yùn)輸組織學(xué) 課程設(shè)計 2 對配送路線優(yōu)化問題的研究 前人已經(jīng)提出不少可行的方法和步驟 本文 在借鑒前人一些方法的基礎(chǔ)上 通過一個實際的研究項目 對路線優(yōu)化進(jìn)一步 加以分析和研究 1 2 問題的提出 1 2 1 配送作業(yè)問題的提出 隨著消費(fèi)需求的增長 市場對貨物流通量的要求也逐漸增大 這就要求有 專門的配送中心對貨物進(jìn)行配送 在沒有配送中心的情況下 由工廠直接運(yùn)送 貨物到用戶 即使采用直接配送方式 其交叉運(yùn)輸是普遍存在的 這就導(dǎo)致了 運(yùn)送路線延長 規(guī)模效益差 運(yùn)輸成本高 如果采用配送的方式 便可消除交 叉運(yùn)輸 如圖 1 1 和圖 1 2 所示 圖圖 1 11 1 交叉運(yùn)輸交叉運(yùn)輸 圖圖 1 21 2 緩解交叉運(yùn)輸緩解交叉運(yùn)輸 工廠 1工廠 2工廠 3 客戶 1客戶 2客戶 3 工廠 1工廠 2工廠 3 配送中心 客戶 1客戶 2客戶 3 交通運(yùn)輸組織學(xué) 課程設(shè)計 3 1 2 2 配送路線優(yōu)化問題的提出 影響配送運(yùn)輸效果的因素很多 1 動態(tài)因素 如車流量變化 道路施工 配送客戶的變動 可供調(diào)動的車輛變化 2 靜態(tài)因素 如配送客戶的分布 區(qū)域 道路交通網(wǎng)絡(luò) 車輛運(yùn)行限制等 各種因素相互影響 很容易造成配送 方面的問題 主要有以下幾個方面 3 1 送貨不及時 主要是信息處理流程時間太長 配送方式落后 2 送貨成本高 這不僅包括企業(yè)的運(yùn)輸成本 也包括客戶的支付成本 3 配送路徑選擇不當(dāng) 這是造成配送問題很重要的一個方面 在這些問題中 有些在短時間內(nèi)無法改變 但對于配送路徑的優(yōu)化比較容 易實現(xiàn)并且效果明顯 選擇了一條合理的配送路線 不僅可以達(dá)到送貨及時的 目標(biāo) 同時也還可以節(jié)約送貨成本 為企業(yè)創(chuàng)造了效益 當(dāng)然 在實際過程中 一條合理的配送路線的選擇 要考慮到很多方面的因素 應(yīng)盡可能綜合考慮影 響配送路線的重要因素 所以解決該問題要站在綜合 全面的角度進(jìn)行考慮 這樣才能作出合理的決策 1 3 本設(shè)計所做的工作及基本結(jié)構(gòu) 1 3 1 本設(shè)計的主要工作 本文以配送路線的優(yōu)化為研究目標(biāo) 以南城平安 深圳 貨運(yùn)公司為研究對 象進(jìn)行深入細(xì)致的分析和討論 主要做了以下的工作 1 在第二章中 針對貨運(yùn)中心配送路線優(yōu)化的研究現(xiàn)狀 了解并討論路 線優(yōu)化的原則 同時還歸納了現(xiàn)有的配送中心路線優(yōu)化的研究方法 指出它的 使用范圍和一些不足之處 最后指出貨運(yùn)中心路線優(yōu)化的意義和目的 2 在第三章中 主要對本文的研究背景 南城平安 深圳 貨運(yùn)公司 作一個現(xiàn)狀的描述 從了解其業(yè)務(wù)狀況入手 掌握它的配送路線和方法 進(jìn)而 分析該公司存在的主要問題 為解決問題提供了依據(jù) 3 在第四章中 針對南城平安 深圳 貨運(yùn)公司配送路線存在的問題 建立相應(yīng)的路線優(yōu)化數(shù)學(xué)模型 并指出該模型的實際意義 4 第五章 圍繞配送路線優(yōu)化模型來展開具體的介紹該模型所使用的方 法 并采用相應(yīng)的計算方法對模型進(jìn)行求解 并利用優(yōu)化后的方法和原始方法 交通運(yùn)輸組織學(xué) 課程設(shè)計 4 做一個比較 最后指出使用該模型 公司是否比以前優(yōu)化了 從而驗證本文的 可行性 5 第六章 總結(jié)本文的主要成果 并列出一些需要進(jìn)一步解決的問題 最后針對南城平安 深圳 貨運(yùn)公司提出幾點(diǎn)自己的看法和意見 1 3 2 本文的基本結(jié)構(gòu) 本文的基本結(jié)構(gòu)可以用下面的框架圖來表示 圖圖 1 31 3 設(shè)計框架結(jié)構(gòu)設(shè)計框架結(jié)構(gòu) 公司配送現(xiàn)狀 業(yè)務(wù)狀況 目前 的配送路線 存在的主要問題 緒 論 研究背景 問題的提出 研究現(xiàn)狀 線路優(yōu)化的原 則 情況分類 意義等 公司配送路線優(yōu)化過程 優(yōu)化思 路 優(yōu)化模型 模型求解過程 基本節(jié)約法 改進(jìn)節(jié)約法 配送計劃軟件 分析結(jié)果 總結(jié) 幾點(diǎn)建議 交通運(yùn)輸組織學(xué) 課程設(shè)計 5 第二章第二章 貨運(yùn)中心配送路線優(yōu)化的研究現(xiàn)狀貨運(yùn)中心配送路線優(yōu)化的研究現(xiàn)狀 2 1 配送路線優(yōu)化的意義 配送運(yùn)輸由于配送方法的不同 其運(yùn)輸過程也不盡相同 影響配送運(yùn)輸?shù)?因素很多 如車流量的變化 道路狀況 客戶的分布狀況和配送中心的選址 道路交通網(wǎng) 車輛額定載重量以及車輛運(yùn)行限制等 在不同情況下 這些因素 都會對配送路線起到不同程度的影響 配送路線的優(yōu)化就是綜合考慮影響配送 運(yùn)輸?shù)母饕蛩?恰當(dāng)?shù)睦矛F(xiàn)有的設(shè)備 及時 安全 方便 經(jīng)濟(jì)的將客戶所 需的物資準(zhǔn)確送達(dá)客戶手中 需根據(jù)不同客戶的特點(diǎn)和要求 選擇不同的設(shè)計 路線 最終達(dá)到節(jié)省時間 運(yùn)行距離和費(fèi)用的目的 在實際生活中 特別是對于一個運(yùn)輸公司來說 配送路線的優(yōu)化有著十分 重要的意義 首先 加快了貨物流通 有利于庫存的周轉(zhuǎn) 在實現(xiàn)了高水平的配送優(yōu)化 路線后 不管是生產(chǎn)企業(yè)還是配送中心都可以完全依靠配送中心的準(zhǔn)時而快捷 的運(yùn)送而不需要保持自己的庫存 或者 生產(chǎn)企業(yè)只需要保持少量保險儲備而 不必留有經(jīng)常儲備 這就可以實現(xiàn)生產(chǎn)企業(yè)多年追求的 零庫存 解放了大量 的儲備資金 也提高了社會經(jīng)濟(jì)效益 其次 節(jié)約了社會運(yùn)力 縮短了貨運(yùn)時間 路線的優(yōu)化 其目的就在于用 最少的運(yùn)力提供最全面的服務(wù) 通過對配送路線的優(yōu)化 不僅解決了送貨在時 間 數(shù)量上的問題 而且使缺貨次數(shù)降至最低 再次 提高了物流服務(wù)水平 配送是隨著物流業(yè)的發(fā)展而發(fā)展起來的一種 新的服務(wù)方式 配送路線的優(yōu)化是物流服務(wù)中很重要的一部分 可以從側(cè)面反 映出物流的服務(wù)水平 2 2 貨運(yùn)中心路線優(yōu)化的方法 為達(dá)到高效率的配送 做到時間少 距離短 成本低 必然要求選擇最佳 交通運(yùn)輸組織學(xué) 課程設(shè)計 6 的配送線路和車輛綜合調(diào)度 很多中外學(xué)者在這領(lǐng)域進(jìn)行了深入的研究 提出 了很多可行的方法 2 2 1 配送路線優(yōu)化問題的簡化 1 旅行商問題 2 這個問題字面上的理解是 有一個推銷員要到 N 個城 市去推銷商品 他要找出一個包含所有 N 個城市的具有最短路程的環(huán)線 TSP 問題的歷史悠久 最早描述是 1759 年歐拉研究的騎士周游問題 即國際象棋棋 盤中的 64 個方格 走訪 64 個方格一次且僅一次 并最終回到起點(diǎn) TSP 問題是運(yùn)籌學(xué) 圖論和組合優(yōu)化中的著名問題 在實際生活中有著廣 泛的應(yīng)用前景 TSP 不僅可以解決最優(yōu)巡回路線等類 TSP 問題 在交通車輛巡 回 學(xué)校教師課程計劃安排 工廠裝配線進(jìn)度管理以及民航機(jī)組人員輪班等問 題上也有著廣泛的應(yīng)用前景 在處理現(xiàn)實生活中的具體問題時 可以對 TSP 附 加一些限制條件 例如在模型中假設(shè)該旅行者的時間有限 進(jìn)而添加相應(yīng)的時 間約束條件等 從而衍生出許多和 TSP 相關(guān)的問題 2 多回路運(yùn)輸問題 3 多回路運(yùn)輸問題在物流中的解釋是對一系列客戶 的需求點(diǎn)設(shè)計適當(dāng)?shù)穆肪€ 使車輛有序的通過它們 在滿足一定的約束條件下 如貨物需求量 發(fā)送量 交貨時間 車輛載重量限制 行駛里程限制等等 達(dá) 到一定的優(yōu)化目標(biāo) 如里程最短 費(fèi)用最少 時間最短 車隊規(guī)模最少 車輛 利用率高等 VRP 問題由 Dantzig 和 Ramser 于 1959 年首次提出 3 該問題一經(jīng)提出 立即引起了運(yùn)籌學(xué) 網(wǎng)絡(luò)分析 物流 計算機(jī)應(yīng)用等學(xué)科專家的極大關(guān)注 成 為運(yùn)籌學(xué)和優(yōu)化科學(xué)研究的前沿和熱點(diǎn)問題 VRP 和 TSP 問題的區(qū)別在于 客戶群體的數(shù)量大 只有一輛車或一條路徑 滿足不了客戶的需求 必須是多輛交通工具以及運(yùn)輸工具的行車順序兩個問題 的求解 4 相對于 TSP 問題 VRP 問題更復(fù)雜 但也更接近實際情況 3 多個旅行商問題 4 由于限制條件的增加 TSP 問題可以衍生出多個 旅行商問題 MTSP 問題就是一個出發(fā)點(diǎn) M 個旅行商的 TSP 即所訪問的客 戶沒有需求 車輛沒有裝載的限制 優(yōu)化目標(biāo)就是要便歷所有的客戶 達(dá)到總 里程最短 VRP 問題是 MTSP 問題的普遍化 當(dāng)客戶的需求不僅僅是被訪問 而是有 交通運(yùn)輸組織學(xué) 課程設(shè)計 7 一定容積和重量的商品的裝載和卸裝 涉及到不同種類和型號或不同載重車輛 的調(diào)度策略時 MTSP 問題轉(zhuǎn)化為 VRP 問題 2 2 2 配送路線的計劃方法 1 精確式算法及其應(yīng)用的局限性 VRP 問題是組合優(yōu)化領(lǐng)域著名的 NP 難題之一 其求解方法一般相當(dāng)復(fù)雜 通常的做法是應(yīng)用相關(guān)技術(shù)將問題分解或者轉(zhuǎn)化為一個或多個已研究過的基本 問題 如旅行商問題 指派問題 運(yùn)輸問題 最短路問題 最大流問題 最小 費(fèi)用最大流問題 中國郵遞員問題等 再使用相對比較成熟的基本理論和方法 進(jìn)行求解 以求得原運(yùn)輸車輛調(diào)度問題的最優(yōu)解或滿意解 精確式算法一般運(yùn)用線性規(guī)劃和非線性規(guī)劃等數(shù)學(xué)規(guī)劃技術(shù) 以便求得最 優(yōu)解 精確式算法一般有以下幾種 分枝定界法 BBP 割平面法 CPA 網(wǎng)絡(luò)流算法 NFA 動態(tài)規(guī)劃方法 DPA 等 精確式算法隨著運(yùn)輸系統(tǒng)的復(fù)雜和調(diào)度目標(biāo)的增加 其計算量呈指數(shù)遞增 使得獲取整個系統(tǒng)的精確最優(yōu)解越來越困難 而用計算機(jī)求解大型化問題的時 間和費(fèi)用又太大 因此 此類優(yōu)化方法現(xiàn)在一般僅用于求解運(yùn)輸調(diào)度的局部優(yōu) 化問題 2 啟發(fā)式算法 為了克服精確優(yōu)化法的不足 可以運(yùn)用一些經(jīng)驗法則來降低優(yōu)化模型的數(shù) 學(xué)精確程度 并通過模仿人的跟蹤校正過程來求取運(yùn)輸系統(tǒng)的滿意解 啟發(fā)式 算法能同時滿足詳細(xì)描繪和求解問題的需要 較精確式算法更加實用 啟發(fā)式 算法一般有以下幾種 最近鄰點(diǎn)法 Nearest Neighbor 5 這是一種用于解決 TSP 問題的啟發(fā) 式算法 方法簡單 但得到的解并不十分理想 可以作為進(jìn)一步優(yōu)化的初始解 求解的過程一共分四步 首先從 O 點(diǎn)開始作為整個回路的起點(diǎn) 然后找到離剛 剛加入到回路的上一節(jié)點(diǎn)最近的一個節(jié)點(diǎn) 并將其加入到回路中 重復(fù)上一步 直到歲有的節(jié)點(diǎn)都加入到回路中 最后 將最后一個加入的節(jié)點(diǎn)和起點(diǎn)連接起 來 構(gòu)成一個 TSP 問題的解 最近插入法 Nearest Insertion 6 最近插入法是另一個 TSP 的求解方 法 它的求解過程也是四步 首先從一個節(jié)點(diǎn)出發(fā) 找到一個最近的節(jié)點(diǎn) 形 交通運(yùn)輸組織學(xué) 課程設(shè)計 8 成一個往返式子回路 在剩下的節(jié)點(diǎn) 尋找一個離子回路中某一節(jié)點(diǎn)最近的節(jié) 點(diǎn) 再在子回路找到一個弧 使弧的兩端節(jié)點(diǎn)到剛尋找到的最近節(jié)點(diǎn)的距離之 和減去弧長的值最小 實際上就是把新找到的節(jié)點(diǎn)加入子回路以后使得增加的 路程最短 就把這個節(jié)點(diǎn)增加到子回路中 重復(fù)以上過程 直到所有的節(jié)點(diǎn)都 加入到子回路中 可以得到相對比較滿意的解 節(jié)約里程法 Saving Algorithm 節(jié)約算法是用來解決運(yùn)輸車輛數(shù)目不確 定的 VRP 問題的最有名的啟發(fā)式算法 它的核心思想是依次將運(yùn)輸問題中的兩 個回路并為一個回路 每次使合并后的總運(yùn)距減小得幅度最大 直到達(dá)到一輛 車的裝載限制時 再進(jìn)行下一輛車的優(yōu)化 優(yōu)化過程分為并行方式和串行方式 兩種 掃描算法 Sweep Algorithm 掃描算法也是求解車輛數(shù)目不限制的 VRP 問題的啟發(fā)式算法 求解過程同樣是四步 以起始點(diǎn)為原點(diǎn)建立極坐標(biāo)系 然 后從最小角度的兩個客戶開始建立一個組 按逆時針方向?qū)⒖蛻糁饌€加入到組 中 直到客戶的需求總量超出了車輛的載重定額 然后建立一個新的組 繼續(xù) 該過程 直到將全部客戶都加入到組中 2 2 3 配送路線優(yōu)化分類 在實際的配送過程中 每天的配送客戶不一定是固定的 這就需要根據(jù)定 單情況 對配送路線進(jìn)行優(yōu)化 我們可以將這些情況進(jìn)行分類 1 某各臨時客戶 不在固定路線上 對于這種情況 如果貨物量不多 可以將該客戶臨時編入到最近的一條固定線路上 如果貨物量很多 可以派出 整車 尋求一條最優(yōu)路徑 圖圖 2 12 1 不在固定線上的小批量臨時用戶不在固定線上的小批量臨時用戶 固定點(diǎn)客戶 A 固定點(diǎn)客戶 B 固定點(diǎn)客戶 C 臨時客戶 E 固定點(diǎn)客戶 D 配送中心 固定點(diǎn)客戶 A 交通運(yùn)輸組織學(xué) 課程設(shè)計 9 說明 小批量臨時客戶 將其納入最近的配送線路 建立臨時點(diǎn) 說明 大批量臨時客戶 臨時建立一條新的配送路線 選擇配送中心到該 用戶的最短路徑 2 某條線路當(dāng)日需要配送的客戶非常少 派車不值得 對于這種情況 可以考慮將其并到其他路線上 合并的原則是在滿足客戶配送要求的前提下 以最低的成本來優(yōu)化路線 圖圖 2 32 3 某路線客戶少的配送情況某路線客戶少的配送情況 說明 圖 2 3 中 客戶 M 和客戶 N 本來是劃分給 C 區(qū)配送路線進(jìn)行配送 的 但是由于當(dāng)日 C 區(qū)線路的客戶太少 派車成本高 故將客戶 M N 按就近 原則暫時分別歸到 B 區(qū)和 C 區(qū) 3 客戶要求緊急 需要緊急配送 在生活中常常會遇到緊急配送的情況 固定點(diǎn)客戶 D 配送中心 客戶 M C 區(qū) 客戶 N A 區(qū)B 區(qū) 臨時客戶 E 配送中心 固定點(diǎn)客戶 B 固定點(diǎn)客戶 C 固定點(diǎn)客戶 A 圖圖 2 22 2 大批量用戶臨時配送大批量用戶臨時配送 交通運(yùn)輸組織學(xué) 課程設(shè)計 10 對于這種情況 我們就得采取緊急的處理措施 一般是在運(yùn)輸配送過程中不裝 別的貨物 中途也不卸車 空車返回 如圖所示 圖圖 2 42 4 緊急配送緊急配送 4 遇到道路緊急情況時 一般采取的是繞行的措施 或者 如果時間充 裕 可以考慮等道路狀況變好后再進(jìn)行配送 2 3 貨運(yùn)中心路線優(yōu)化原則 任何一個貨運(yùn)中心在制定配送路線時 應(yīng)根據(jù)客戶的分布 道路的交通情 況 貨運(yùn)中心本身位置等因素 先制定一條或幾條固定路線 配送時按照不在 同一線路的客戶 其貨物不能組成一車的原則 把貨物進(jìn)行分組 線路的劃分 主要考慮以下幾點(diǎn) 1 集中原則 位置比較集中的客戶盡量劃分在一條線路上 這是路線優(yōu) 化的基礎(chǔ) 不僅可以極大的節(jié)約運(yùn)力和運(yùn)費(fèi) 而且可以配送的及時性 2 線路最少原則 指在運(yùn)力允許的條件下 盡量用最少的線路劃分客戶 在實際運(yùn)用中 減少一條線路 將會為企業(yè)節(jié)約極大的成本 3 線路最短原則 劃分線路時 應(yīng)盡量使線路最短 配送中心 臨時客戶需緊急配送的客戶 交通運(yùn)輸組織學(xué) 課程設(shè)計 11 第三章第三章 南城平安 深圳 貨運(yùn)公司配送線路現(xiàn)狀南城平安 深圳 貨運(yùn)公司配送線路現(xiàn)狀 3 1 公司業(yè)務(wù)狀況 3 1 1 公司簡介 南城平安 深圳 貨運(yùn)公司成立于 1995 年 毗鄰長城儲運(yùn)貨代市場 地理 位置優(yōu)越 交通便利 公司目前擁有 20 尺貨柜車 40 尺貨柜車 45 尺貨柜車 5 噸 8 噸 10 噸大型車隊 貨物提貨點(diǎn)多處自備吊車 叉車 公司采用先進(jìn)的管理機(jī)制 完善的交通信息網(wǎng) 成熟的物流管理 倉儲 搬運(yùn) 資訊 服務(wù) 公司始終堅持 客戶至上 時間第一 的原則 經(jīng)過 10 年的努力 該公司已經(jīng)達(dá)到多數(shù)客戶要求的高速 高效 安全 低價格 優(yōu)質(zhì) 的跟蹤服務(wù)目的 為客戶及其他貨運(yùn)站提供了充足 快捷的運(yùn)輸車輛 公司主要承接深圳至上海 杭州 北京 昆明 重慶 呼和浩特等全國各 地的國內(nèi)公路貨運(yùn) 鐵路運(yùn)輸 航空運(yùn)輸及深港散件業(yè)務(wù) 同時也受理長短途 搬家遷廠等業(yè)務(wù) 公司自備人貨車多輛 24 小時為客戶服務(wù) 3 1 2 公司的業(yè)務(wù)狀況 目前 公司采用雙回程營運(yùn) POS 實時追蹤 門對門服務(wù) 全保聯(lián)保 誠 信價平的運(yùn)輸策略 1 公路貨運(yùn)可至汽車所有到達(dá)的所有城市 當(dāng)日發(fā)車 專線直達(dá) 2 鐵路運(yùn)輸服務(wù)項目 行包專列 特快包裹物品托運(yùn) 中鐵快運(yùn) 集裝 箱 車皮運(yùn)輸及到貨提付等業(yè)務(wù) 3 航空貨運(yùn)直達(dá)全國通航的四十余個城市 4 深港散件 24 小時內(nèi)收到 5 提供大 中 小車輛進(jìn)行搬家遷廠 良好的物流將增加企業(yè)的市場竟?fàn)幠芰?南城平安提供的服務(wù)主要有 交通運(yùn)輸組織學(xué) 課程設(shè)計 12 1 采用門對門優(yōu)質(zhì)服務(wù) 2 任何司乘人員都嚴(yán)格遵守廠規(guī)廠紀(jì) 配合工作人員完成裝貨事宜 3 準(zhǔn)時 安全的將貨物送到客戶指定地點(diǎn) 并填好司乘人員追蹤單 4 公司的電腦網(wǎng)絡(luò)部可免費(fèi)為客戶進(jìn)行電腦維護(hù) 安裝 網(wǎng)站制作及對 員工進(jìn)行電腦應(yīng)用軟件的培訓(xùn) 3 2 公司的配送路線 該公司的運(yùn)送方式是分送式運(yùn)輸 也就是一個供應(yīng)點(diǎn)對應(yīng)多個客戶的共同 運(yùn)輸 其中包括公路貨運(yùn) 鐵路貨運(yùn)和航空貨運(yùn) 3 2 1 國內(nèi)主要城市配送方式 該公司在國內(nèi)主要城市的配送主要以鐵路和航空運(yùn)輸為主 公路占少數(shù)一 部分 主要承接跨省的長途貨物運(yùn)輸 其運(yùn)輸量相對比較大 運(yùn)輸范圍已達(dá)到 全國各大中城市 如上海 北京 天津 南京 合肥 武漢 蘭州 長沙等 其配送方式一般采取點(diǎn)對點(diǎn)式 在運(yùn)輸距離較遠(yuǎn)并且條件允許的情況下 可以 采取轉(zhuǎn)運(yùn) 采用鐵路 航空 航空 鐵路 鐵路 航空 公路 航空 鐵路 公路等混合運(yùn)輸方式 3 13 1 國內(nèi)主要城市配送路線國內(nèi)主要城市配送路線 交通運(yùn)輸組織學(xué) 課程設(shè)計 13 3 2 2 省內(nèi)主要配送方式 省內(nèi)運(yùn)輸主要以公路運(yùn)輸為主 公路貨運(yùn)主要承接中短途貨物的運(yùn)輸 運(yùn) 輸量相對較小 也有一部分長途運(yùn)輸 在省內(nèi)各個城市之間的送貨以簡單的節(jié) 約法思想進(jìn)行車輛的調(diào)度 圖圖 3 23 2 省內(nèi)主要城市的配送路線省內(nèi)主要城市的配送路線 在深圳市內(nèi) 在貨運(yùn)量不大的情況下 運(yùn)送方式主要以專線直達(dá)為主 一 戶一送 運(yùn)送范圍也大部分集中在深圳市及周邊地區(qū) 如圖 3 3 所示 圖圖 3 33 3 市內(nèi)主要城市的配送路線市內(nèi)主要城市的配送路線 深圳 交通運(yùn)輸組織學(xué) 課程設(shè)計 14 3 3 存在的主要問題及分析 雖然目前公司發(fā)展迅速 物流業(yè)務(wù)也逐步趨于完善 但通過對這個公司的 深入調(diào)查和了解 我們還是可以發(fā)現(xiàn)該公司存在的一些問題 主要表現(xiàn)在 1 調(diào)度問題 車輛調(diào)度是否合理直接影響到運(yùn)輸里程和運(yùn)輸成本 在配送路線的制定上 該公司以基本的節(jié)約法為主要依據(jù) 但節(jié)約法也有其自身的不足 主要體現(xiàn)在 以下幾個方面 第一 運(yùn)用節(jié)約法選擇配送路線過于強(qiáng)調(diào)節(jié)約里程 而沒有考慮行程中的 時間因素 在許多情況下 時間更能決定物流配送的成本與服務(wù)質(zhì)量 例如城 市間配送時對高速公路的選擇 城市內(nèi)部上下班時間的道路擁擠 一個巡回配 送過程中的時間長短 直接影響配送人員的精神狀態(tài) 而配送人員的精神狀態(tài) 又與交通事故和配送錯誤相連 所以時間對配送路線的選擇有時更重要 第二 利用節(jié)約法選擇配送路線不能對客戶的需求進(jìn)行靈活多變的處理 由于現(xiàn)代的消費(fèi)者的需求趨于個性化 引起企業(yè)的生產(chǎn) 銷售和配送也愈來愈 傾向于小小批量 大多品種 多批次 而節(jié)約法更適合于需求穩(wěn)定或是需求時 間不緊迫 這顯然不能滿足現(xiàn)代多變的市場環(huán)境 最后值得一提的是 節(jié)約法在制定的配送路線并不是總的路程最短 原因 是節(jié)約法一方面要縮短總路程 另一方面又要充分利用車輛的運(yùn)輸空間 載重 容積 減少配送車次 而且只要在前一條預(yù)設(shè)路線上運(yùn)行的配送車輛的運(yùn)輸空 間允許 就必須按節(jié)約路程的大小順序進(jìn)行選擇而不考慮其他預(yù)設(shè)路線 在事 實情況下選擇的路線并不能 節(jié)約 路程和有效利用運(yùn)輸空間 而且運(yùn)輸?shù)能?次也不一定減少 2 其它問題 第一 GIS 問題 眾所周知 車輛優(yōu)化調(diào)度需要一套詳盡豐富同時實時更 新的地理信息系統(tǒng) GIS 支持 該公司面臨的最大問題是 GIS 的建設(shè)問題 雖然目前該公司已經(jīng)有了一套電子地圖 但從使用結(jié)果來看 并不理想 一是 信息量太少 許多街道沒有標(biāo)出 尤其是小區(qū)小街或則郊區(qū)線路 二是系統(tǒng)更 新速度太慢 維護(hù)跟不上 許多地區(qū)已經(jīng)更名或改變 但在電子地圖里還沒有 變化 交通運(yùn)輸組織學(xué) 課程設(shè)計 15 第二 技術(shù)裝備落后問題 從公司的現(xiàn)狀來看 技術(shù)裝備的落后主要表現(xiàn) 在缺少高效的裝卸搬運(yùn)設(shè)備 如叉車 吊車 在貨運(yùn)中心 好多裝卸搬運(yùn)工作 還要人工來完成 第三 局部區(qū)域內(nèi)貨運(yùn)量的不平衡 這是一個普遍的問題 由于個地區(qū)經(jīng) 濟(jì)發(fā)展水平的不同 這些地區(qū)間的貨運(yùn)量就不可能等同 這就導(dǎo)致了貨運(yùn)車輛 的空載現(xiàn)象 從而導(dǎo)致運(yùn)力的下降 造成運(yùn)輸成本的增加 由于該公司是貨物 的集散中心 這就造成了從貨運(yùn)中心向客戶運(yùn)送時經(jīng)常滿載 而返程空載的現(xiàn) 象 并隨著貨運(yùn)周轉(zhuǎn)量的增加 空載里程也隨之增長 在這些問題中 有些問題是在短時間內(nèi)無法解決的 如局部區(qū)域內(nèi)貨運(yùn)量 的不平衡 GIS 問題等 但對于車輛調(diào)度方面的問題我們可以采取相應(yīng)的措施 使得車輛的調(diào)度更加合理 這是可行的 如何解決該公司的運(yùn)輸路線問題 我 們將在以后的幾章里具體介紹 交通運(yùn)輸組織學(xué) 課程設(shè)計 16 第四章第四章 貨運(yùn)中心配送路線的優(yōu)化設(shè)計貨運(yùn)中心配送路線的優(yōu)化設(shè)計 4 1 優(yōu)化思路 在研究該公司配送路線優(yōu)化時 可以先考慮該公司在深圳市內(nèi)的配送路線 并由深圳市內(nèi)推廣至整個廣東省 所以 本文主要以研究深圳市及周邊地區(qū)城 市的配送路線為主 由前面的介紹我們可知 該公司在省內(nèi)配送路線的制定依據(jù)是基本節(jié)約里 程法 本章運(yùn)用節(jié)約法分析市內(nèi)的配送路線 4 2 市內(nèi)配送優(yōu)化 4 2 1 主要狀況 南城平安 深圳 貨運(yùn)公司位于廣東省深圳市 9 我們以該公司在深圳市 及周邊地區(qū)的貨物運(yùn)輸為例 取其中的布吉 橫崗 龍華 平湖 風(fēng)崗 龍崗 坪山 坑梓 新圩 石巖 沙井 長安 清溪 樟木頭 大朗等十五個城市作 為配送路線研究的背景 設(shè)貨運(yùn)中心 深圳 為 Po 各個客戶分別為 Pk k 1 2 15 已知該 公司有 5t 8t 10t 的車型可用 發(fā)送的最大發(fā)送距離為 200 20 公里 各個客戶的地理位置如下圖 交通運(yùn)輸組織學(xué) 課程設(shè)計 17 圖圖 4 14 1 各客戶的相對位置各客戶的相對位置 表 4 1 客戶及貨運(yùn)量對照表 單位 噸 客 戶 布 吉 橫 崗 龍 華 平 湖 風(fēng) 崗 龍 崗 坪 山 坑 梓 新 圩 石 巖 沙 井 長 安 清 溪 樟 木 頭 大 朗 P k P1P2P3P4P5P6P7P8P9P10P11P12P13P14P15 貨運(yùn)量 t 1 62 02 12 51 51 21 41 62 01 32 01 72 21 62 4 4 2 2 南城平安 深圳 貨運(yùn)公司配送路線優(yōu)化模型 根據(jù)節(jié)約法的基本思路 針對南城平安 深圳 貨運(yùn)公司 我們可以建立 數(shù)學(xué)模型如下 2 配送中心 P0 可用車輛集合是 q k 1 2 m q 為載重量 用戶 gi i 1 2 n gi為用戶 i 的貨運(yùn)量 如果可以混裝 則有 Max g i q 用戶 i 到用戶 j 的最短距離記為 d i j 定義 0 1 變量如下 Yk i 1 表示 I 的用戶由車輛 k 完成 否則記為 Yk i 0 Xi j k 1 表示車輛 k 從 i 行駛到點(diǎn) j 否則記為 Xi j k 0 Min Z C y X y k 4 1 其中 g i y k q k 4 i k 2 y k i 1 i 1 2 n 4 3 k 交通運(yùn)輸組織學(xué) 課程設(shè)計 18 y k i 1 or 0 i 0 1 n k X i j k y k j j 0 1 n 4 i k 4 X i j k y k i i 0 1 n 4 j k 5 X i j k 1 or 0 i j 0 1 n k 公式中 C i j表示從點(diǎn) i 到點(diǎn) j 的運(yùn)輸成本 含義可以是距離 費(fèi)用 時間等 示情況而定 該問題的求解思想是在保證一條線路上各用戶的貨運(yùn)量 不大于車 輛的載重的前提下 連接點(diǎn)對 公式中 C i j表示從點(diǎn) i 到點(diǎn) j 的運(yùn)輸成本 含義可以是距離 費(fèi)用 時間等 示情況而定 該問題的求解思想是在保證一條線路上各用戶的貨運(yùn)量不大于車 輛的載重的前提下 連接點(diǎn)對 首先 把各個點(diǎn)單獨(dú)與配送中心相連 構(gòu)建僅含一個點(diǎn)的初始路線 得到 費(fèi)用 Z Co i Ci o 然后計算如果連接點(diǎn) i 和 j 到同一線路上得到的節(jié)約值 S i j Co i Ci o Co j Cj o Co i Cj o Ci j Ci o Co j Ci j or S i j Cj o Co i Cj i S i j 越大 說明把點(diǎn) i 和 j 連接在一起時 節(jié)約的費(fèi)用越多 如果 S i j 為負(fù)值 表示連接后費(fèi)用增加 此時就不應(yīng)該把點(diǎn) i 和點(diǎn) j 連接到同一條線路上 來 交通運(yùn)輸組織學(xué) 課程設(shè)計 19 第五章第五章 南城平安 深圳 貨運(yùn)公司線路優(yōu)化模型的求解南城平安 深圳 貨運(yùn)公司線路優(yōu)化模型的求解 5 1 節(jié)約法的基本思想與步驟 5 1 1 節(jié)約法的基本思想 在第二章的第二節(jié)里提到過配送路線的優(yōu)化方法 其中最具代表性的就是 由 Clarke 和 Wright 提出的節(jié)約里程法 2 下面我們來分析節(jié)約法的基本思想 假設(shè)配送中心 P0 M 個用戶分別是 P1 P2 Pm Pi和 Pj之間的最短距 離是 di j 且 di j已知 i j 1 2 3 m 如果發(fā)送車輛的噸位已知 并且每一輛車都可以滿載 則研究的目標(biāo)轉(zhuǎn)化為 使所有參加發(fā)送的車輛的總發(fā)送距離在滿足約束條件的基礎(chǔ)上最小 在考慮配送計劃時 首先假定在任何情況下 運(yùn)輸網(wǎng)絡(luò)中的任意兩點(diǎn)都有路 徑可通 并且都有最短路線 如圖 a b c 所示 Pi Pj Pi P0 Pj Pj Pi P0 交通運(yùn)輸組織學(xué) 課程設(shè)計 20 a b c 圖圖 5 15 1 節(jié)約法基本思想節(jié)約法基本思想 如果兩點(diǎn)的運(yùn)輸不通暢 則可以將這些情況轉(zhuǎn)化為相應(yīng)的約束條件列入方 程組中 然后求解 如圖 5 1 所示 如果把原來 a 的運(yùn)輸路線由 P0 Pi 1 Pi P0和 P0 Pj 1 Pj P0改為 b 的 P0 Pi 1 Pi Pj 1 Pj P0 則改動之后的節(jié)約量 為 Si j d0 i d0 j di j 圖圖 5 25 2 典型的節(jié)約方案 典型的節(jié)約方案 1 1 如圖 5 2 如果將原來 a 中由 P0分別向 Pi 和 Pj兩點(diǎn)配送貨物的往返運(yùn) 輸路線 P0 Pi P0 和 P0 Pj P0改為 b 的 P0 Pi Pj P0 則總發(fā)送距離由 原來的 2 d0 i d0 j 改變?yōu)?d0 i d0 j di j 也就是說 由于連接 Pi和 Pj而得到的節(jié) 約量是 2 d0 i d0 j d0 i d0 j di j d0 i d0 j di j 圖 5 3 典型的節(jié)約方案 2 5 1 2 模型的求解步驟 根據(jù)節(jié)約法的原理和上述的基本思路 我們可以設(shè)計求解配送路線優(yōu)化模 P0P0 Pi Pj Pi Pj Pi Pj Pi P0 Pj 1 P0 Pi 1 Pj 1 Pi 1 Pj 交通運(yùn)輸組織學(xué) 課程設(shè)計 21 型的步驟如下 第一 計算節(jié)約值 S i j 令集合 S S i j S i j 0 第二 集合中的元素按從大到小的順序排序 第三 如果集合 S 則計算結(jié)束 否則對第一個元素 S i j 考查對應(yīng)的 i j 是否滿足下列條件之一 點(diǎn) I 和點(diǎn) j 都不在已經(jīng)構(gòu)成的線路上 點(diǎn) I 和點(diǎn) j 都在已經(jīng)構(gòu)成的線路上 但是不與配送中心相連 點(diǎn) I 和點(diǎn) j 都在已經(jīng)構(gòu)成的兩個線路上 都不與配送中心相連 其中一 個是線路的起點(diǎn) 另一個是線路的終點(diǎn) 轉(zhuǎn)下一步 否則轉(zhuǎn)步驟 考查點(diǎn) I 和點(diǎn) j 連接后線路上總的貨運(yùn)量 Q 如果 Q q 轉(zhuǎn)下一步 否 則轉(zhuǎn)步驟 連接點(diǎn) I 和 j 到同一條線路上 令 S S S i j 轉(zhuǎn)步驟 5 2 簡單節(jié)約法的求解 5 2 1 求解過程分析 1 初始方案 對每一個客戶分別派車 空車返回 總的路線為 15 條 總路程 S 2 D0 i 1106km 15 1i 派車情況 需 5t 的車 15 輛 2 節(jié)約里程的線路優(yōu)化方案 表表 5 15 1 各個客戶之間的距離表 單位 公里 各個客戶之間的距離表 單位 公里 Po 7P1 1412P2 221626P3 20141417P4 282219228P5 333120382018P6 37362647313013P7 444230503330129P8 交通運(yùn)輸組織學(xué) 課程設(shè)計 22 545042543731212719P9 32263611273147575961P10 5146563145476475767420P1 1 565160354747647676722510P12 42363234221521343222405249P13 5144443631253749463637433816P14 625659434541566865553835263519P15 第一步 計算節(jié)約里程 S i j Po i Po j Pi j 結(jié)果如下 表表 5 25 2 節(jié)約里程表 單位 公里 節(jié)約里程表 單位 公里 Q i Po 1 67P1 2 0149P2 2 1221310P3 2 520132025P4 1 52813232840P5 1 233927173343P6 1 43783212263557P7 1 6449281631426572P8 2 0541126223751666479P9 1 332131043252918121725P10 2 0511294226322013193163P11 1 7561110432937251724386397P12 2 242132430405554455474344149P13 1 65114213740544739496946596977P14 2 4621317413749393141615678926994P15 第二步 根據(jù)上表計算所得的結(jié)果 將節(jié)約值從大到小分類 如下表 表表 5 35 3 節(jié)約里程順序表 單位 公里 節(jié)約里程順序表 單位 公里 P11P12 97 P7P8 72 P10P11 63 P5P4 54P6P14 47P3P11 42P6P15 39P5P7 35 交通運(yùn)輸組織學(xué) 課程設(shè)計 23 P14P15 94P12P14 69P10P12 63P6P13 54P10P14 46P8P15 41P7P14 39P10P13 34 P12P15 92P13P15 69P9P15 61P8P13 54P7P13 45P11P13 41P9P12 38P4P6 33 P8P9 79P9P14 69P11P14 59P5P9 51P3P12 43P3P15 41P5P12 37P2P7 32 P11P15 78P6P9 66P6P7 57P5P15 49P5P6 43P4P13 40P4P15 37P5P11 32 P13P14 77P6P8 65P10P15 56P8P14 49P3P10 43P4P14 40P4P9 37P4P8 31 P9P13 74P7P9 64P5P13 55P12P13 49P5P8 42P4P5 40P3P14 37 第三步 在節(jié)約里程表中選出最大的節(jié)約格 P11P12 97 說明將用戶 P11 P12連接所獲得的節(jié)約量最大 所以將初始方案中的用兩輛車分別向 P11 P12送貨 改為用一輛車向 P11 P12巡回送貨 運(yùn)輸距離 S P0 11 P11 12 P12 0 51 10 56 117km 200km 運(yùn)量 Q Q11 Q12 2 0 1 7 3 7 故用 5t 車運(yùn)送 進(jìn)一步修正方案 在節(jié)約里程表中尋找與 P11 P12有關(guān)的節(jié)約量最大的格 子 符合條件的是 P12P15 92 考慮如果將其并入該路線是否可行 此時運(yùn)輸 距離 S P0 11 P11 12 P12 15 P15 0 51 10 26 62 149km 200km 運(yùn)量 Q Q11 Q12 Q15 2 0 1 7 2 4 3 7 故用 5t 車運(yùn)送 并入可行 以同樣的方法繼續(xù)尋找這樣的格子 我們可以將點(diǎn) P14 P13并入該路線 此時運(yùn)輸距離 S1 P0 11 P11 12 P12 15 P15 14 P14 13 P13 0 51 10 26 19 16 42 164km 200km 運(yùn)量 Q Q11 Q12 Q15 Q14 Q13 2 0 1 7 2 4 1 6 2 2 9 9t 故用 10t 車運(yùn)送 由于裝載量的限制 如果再將其中的一用戶并入該路線 勢 必有 Q 10t 而該公司沒有 10t 以上的車型 故此路線配送結(jié)束 第一個計劃 配送完成 結(jié)果如下 表表 5 45 4 第一個配送計劃結(jié)果第一個配送計劃結(jié)果 配送車型5t 8t 10t 可用的車輛數(shù) 輛 70 60 80 分配的車輛 輛 11 0 1 在剩下的節(jié)約格子里尋找里程最大的格子 符合條件的是 P8P9 79 將其連 接 此時運(yùn)輸距離 S2 P0 8 P8 9 P9 0 44 19 54 119km 200km 運(yùn)量 Q Q8 Q9 1 6 2 2 3 8t 故用 5t 車運(yùn)送 并入可行 按同樣的方法可以把 P7 P6 P5依次并入該路線 此時運(yùn)輸距離 S P0 5 P5 6 P6 9 P9 8 P8 7 P7 0 28 18 21 19 9 37 132km 200km 運(yùn)量 Q Q5 Q6 Q7 Q8 Q9 1 5 1 2 1 4 1 6 2 0 7 7t 故用 8t 車運(yùn) 送 考慮到如果再將 P4并入 Q 10 2t 10t 超出了車型載重量 故不可行 交通運(yùn)輸組織學(xué) 課程設(shè)計 24 第二個配送計劃結(jié)束 結(jié)果如下 表表 5 55 5 第二個配送計劃結(jié)果第二個配送計劃結(jié)果 配送車型5t 8t 10t 可用的車輛數(shù) 輛 70 60 80 分配的車輛 輛 5 1 1 在剩下的節(jié)約格子里繼續(xù)尋找里程最大的格子 符合條件的是 P3P10 43 將其連接 同理可以依次