楊拓論文初稿武漢煙草集團(tuán)配送線路路徑優(yōu)化設(shè)計(jì)(最終版).doc

目目 錄錄 摘摘 要要 2 2 ABSTRACTABSTRACT 3 3 第第 1 1 章章 緒論緒論 4 4 1 1 選題背景 4 1 2 研究意義 5 1 3 研究?jī)?nèi)容與技術(shù)路線 5 2 2 武煙集團(tuán)配送線路的現(xiàn)狀與分析武煙集團(tuán)配送線路的現(xiàn)狀與分析 6 6 2 1 武煙集團(tuán)基本情況 6 2 2 武煙集團(tuán)煙草配送線路的發(fā)展現(xiàn)狀 6 2 3 武煙集團(tuán)煙草配送線路的分析 7 2 4 武煙集團(tuán)配送線路存在的問題 8 第第 3 3 章章 武煙集團(tuán)配送線路路徑優(yōu)化武煙集團(tuán)配送線路路徑優(yōu)化 8 8 3 1 問題提出與描述 8 3 2 解決思路 9 3 3 具體實(shí)現(xiàn) 9 第第 4 4 章章 總結(jié)與展望總結(jié)與展望 1919 4 1 主要研究工作總結(jié) 19 4 2 未來展望 20 參考文獻(xiàn)參考文獻(xiàn) 2121 致致 謝謝 2222 2 摘摘 要要 隨著競(jìng)爭(zhēng)環(huán)境的變化 物流作為 第三利潤源 開始逐漸被引入我國的煙草行業(yè) 其中 煙草配 送作為煙草物流系統(tǒng)的重要組成部分 它的發(fā)展與創(chuàng)新關(guān)系到煙草企業(yè)的核心競(jìng)爭(zhēng)力 現(xiàn)階段煙草企 業(yè)的核心競(jìng)爭(zhēng)力主要由兩方面構(gòu)成 其一是產(chǎn)品技術(shù) 也就是生產(chǎn)國式卷煙所需的各項(xiàng)技術(shù) 其二就 是物流配送技術(shù) 在生產(chǎn)設(shè)備 原輔材料趨于同質(zhì)的今天 如何做到比競(jìng)爭(zhēng)對(duì)手更及時(shí) 更有效地滿 足市場(chǎng)需要 已成為企業(yè)競(jìng)爭(zhēng)的重要內(nèi)容 二者相比 物流配送技術(shù)更具戰(zhàn)略價(jià)值 然而配送線路規(guī) 劃的成功與否直接影響配送的效率與成本 所以 對(duì)配送線路的優(yōu)化 成為煙草企業(yè)提高核心競(jìng)爭(zhēng)力 的重要手段 本文以武漢煙草集團(tuán)配送線路作為研究對(duì)象 分析其配送線路的現(xiàn)狀與問題 建立合理的數(shù)學(xué)模 型 實(shí)現(xiàn)配送路線的合理選擇 優(yōu)化資源配置 全面提升卷煙配送效率 降低配送成本 從而提升武 漢煙草集團(tuán)市場(chǎng)競(jìng)爭(zhēng)力 關(guān)鍵詞 武煙集團(tuán) 煙草配送 車輛線路優(yōu)化 路徑優(yōu)化 3 ABSTRACT As competition environment changes logistics as third profit source gradually began to were introduced in China s tobacco industry Among them the tobacco distribution as tobacco logistics system is the important component of its development and innovation is vital to tobacco enterprise core competitiveness At present the core competitiveness of tobacco enterprises mainly by two aspects constitute one is the product technology is also the producer type cigarette all the necessary technology Second is the logistics technology the production equipment raw material tends to coessential today how to do better than the competition more seasonable more effectively meet the needs of the market has become the important content of the enterprise competition Both logistics technology compared to more strategic value But the success of distribution line planning directly influences the efficiency and cost delivery therefore the optimization of distribution lines become tobacco enterprise important means of improving the core competitive power Taking wuhan tobacco group distribution lines as the research object analyzes its present situation and problems of distribution lines establish a rational mathematical model the reasonable choice of distribution route optimize the allocation of resources improve overall cigarette distribution efficiency reduce the distribution costs and thus enhance wuhan tobacco group market competitiveness Keywords Tobacco distribution Vehicle routes optimization Path optimization 4 第第 1 1 章章 緒論緒論 1 1 選題背景 煙草行業(yè)作為國民經(jīng)濟(jì)發(fā)展和國家稅收的重要產(chǎn)業(yè)之一 已成為國家重視的基礎(chǔ)產(chǎn)業(yè) 物流作為 企業(yè)的第三利潤源泉 是企業(yè)降低成本 提高利潤的重要領(lǐng)域 因此 煙草物流成本理論已成為物流 分支理論中的一個(gè)熱點(diǎn) 科學(xué)運(yùn)作煙草物流配送是煙草物流成本能否得到最大程度降低的一個(gè)重要因 素 從某種意義上來說 煙草物流配送水平的高低將直接決定著煙草物流成本的高低 進(jìn)而影響到煙 草企業(yè)的經(jīng)濟(jì)效益 隨著競(jìng)爭(zhēng)環(huán)境的變化 卷煙流通格局發(fā)生了較大的變化 尤其是經(jīng)營體制的轉(zhuǎn)變和個(gè)體工商戶的 迅速發(fā)展 使卷煙購銷經(jīng)營渠道和經(jīng)營方式都發(fā)生了很大的變化 相應(yīng)的卷煙物流配送模式也發(fā)生了 重要改變 武煙集團(tuán)作為全國知名的煙草企業(yè) 借鑒國外先進(jìn)經(jīng)驗(yàn) 結(jié)合武漢本地實(shí)際 提出了管理 與服務(wù)相結(jié)合 以服務(wù)為主的 全面訪銷 全面配送 專銷結(jié)合 訪送分離 的城市卷煙銷售網(wǎng)絡(luò)模式 并把網(wǎng)絡(luò)路線建設(shè)作為集團(tuán)工作的重中之重來抓 作為 一把手工程 發(fā)展工程 生命工程 來抓 1 2 研究意義 由于市場(chǎng)競(jìng)爭(zhēng)日趨激烈 企業(yè)為了降低成本 提高自身競(jìng)爭(zhēng)力逐漸采用 零庫存 的運(yùn)作方式 消費(fèi)者對(duì)產(chǎn)品需求多樣化和快速變化 企業(yè)相應(yīng)必須采取 少批量 多批次 的進(jìn)貨和生產(chǎn)方式 另 外還有對(duì)企業(yè)全面質(zhì)量管理的要求等等因素 這些都要求更快 更頻繁地運(yùn)輸少量 多批次的貨物 直接或間接地導(dǎo)致了配送成本的增加 配送成本往往占據(jù)整個(gè)物流成本的一半以上 因此 提高配送 效率具有巨大的經(jīng)濟(jì)效益 如何降低配送成本也因此成為一個(gè)備受關(guān)注的問題 目前 我國煙草物流配送在理論和實(shí)際運(yùn)作上都嚴(yán)重滯后于國外發(fā)達(dá)國家 究其原因是 一方面 由于我國煙草企業(yè)長(zhǎng)期是國營體制 大鍋飯思想使得煙草企業(yè)的管理思想僵化 管理者對(duì)企業(yè)物流配 送不夠重視 造成煙草物流配送發(fā)展嚴(yán)重滯后于煙草市場(chǎng)需求的擴(kuò)大 另一方面 由于物流這門學(xué)科 引入中國的時(shí)間并不長(zhǎng) 致使國內(nèi)學(xué)者對(duì)煙草物流配送的理論研究嚴(yán)重滯后于國外同行 煙草物流配 送理論的缺失在實(shí)際企業(yè)管理中表現(xiàn)為 企業(yè)無法科學(xué)地規(guī)劃本企業(yè)的煙草物流配送 往往憑經(jīng)驗(yàn)去 運(yùn)作企業(yè)物流配送 致使煙草物流配送成本長(zhǎng)期居高不下 出現(xiàn)客戶抱怨頻繁等問題 因此 提高煙 草物流配送運(yùn)作水平對(duì)于提高我國煙草企業(yè)核心競(jìng)爭(zhēng)力具有重要的戰(zhàn)略意義 而提高配送效率與降低配送成本的實(shí)現(xiàn) 就必須進(jìn)行配送路線路徑的優(yōu)化 物流配送路線路徑優(yōu) 化是物流系統(tǒng)中的關(guān)鍵一環(huán) 對(duì)配送路線路徑的優(yōu)化 可以提高物流經(jīng)濟(jì)效益 實(shí)現(xiàn)物流科學(xué)化 因此 從煙草企業(yè)的層面上看 煙草配送線路的設(shè)計(jì)與優(yōu)化是關(guān)系到企業(yè)經(jīng)濟(jì)效益實(shí)現(xiàn) 關(guān)系到 卷煙零售戶的滿意度提高 進(jìn)而關(guān)系到企業(yè)核心競(jìng)爭(zhēng)力提升和生存 發(fā)展的大問題 配送路徑規(guī)劃的 成功與否 將直接影響配送成本高低 工作效率快慢和服務(wù)質(zhì)量?jī)?yōu)劣 關(guān)系到大物流建設(shè)的整體優(yōu)勢(shì) 能否實(shí)現(xiàn) 5 1 3 研究?jī)?nèi)容與技術(shù)路線 煙草配送線路作為聯(lián)系煙草企業(yè)和消費(fèi)者的紐帶 是煙草物流建設(shè)的重要內(nèi)容 通過對(duì)配送線路 的優(yōu)化 可以有效提升煙草物流的運(yùn)作水平 有力的配合我國卷煙銷售網(wǎng)絡(luò)的建設(shè)工作 有利于 電 話訂貨 電子結(jié)算 網(wǎng)上配貨 現(xiàn)代物流 的新型卷煙經(jīng)營模式在全國的推廣 基于此 本文在已有 的研究基礎(chǔ)上 通過大量現(xiàn)場(chǎng)調(diào)研 深入分析了煙草商業(yè)配送線路優(yōu)化問題 并重點(diǎn)討論了相應(yīng)的優(yōu) 化模型的構(gòu)建和應(yīng)用 論文主要包括以下內(nèi)容 第一章 緒論 簡(jiǎn)要分析了介紹本選選題的背景和研究意義 第二章 武煙集團(tuán)物流配送線路的現(xiàn)狀與分析 第三章 針對(duì)武煙集團(tuán)配送線路路徑存在的問題 對(duì)其進(jìn)行合理優(yōu)化 選擇算法 建立數(shù)學(xué)模型 求解出結(jié)果 第四章 總結(jié)與展望 總結(jié)本文主要工作 分析本文的優(yōu)點(diǎn)和進(jìn)一步解決的問題 2 武煙集團(tuán)配送線路的現(xiàn)狀與分析武煙集團(tuán)配送線路的現(xiàn)狀與分析 2 1 武煙集團(tuán)基本情況 武漢煙草 集團(tuán) 有限公司組建于 1995 年 是全國煙草行業(yè) 36 家重點(diǎn)企業(yè)之一和全行業(yè) 5 家擁 有國家級(jí)技術(shù)中心的企業(yè)之一 也是國家煙草專賣局確認(rèn)的 10 重點(diǎn)技改企業(yè) 集團(tuán)總部位于享有 九 省通衢 之稱的華中重鎮(zhèn)武漢 集團(tuán)現(xiàn)有員工 5860 人 資產(chǎn)總額 73 億元 下設(shè)武漢卷煙廠 三峽卷煙 廠 紅安卷煙廠 廣水卷煙廠 武煙集團(tuán)核心企業(yè)武漢卷煙廠是中國歷史最悠久的煙草企業(yè)之一 其 前身是創(chuàng)建于 1916 年的南洋兄弟煙草公司漢口分公司 集團(tuán)現(xiàn)主要生產(chǎn) 紅金龍 黃鶴樓 等品牌系列卷煙 與英美煙草公司合作生產(chǎn) 順百利 茂大 品牌雪茄煙 是行 業(yè)內(nèi)唯一一家能生產(chǎn)烤煙型 混合型卷煙和雪茄煙產(chǎn)品的企業(yè) 近年來 集團(tuán)探索出 全面訪銷 全面配送 專銷結(jié)合 訪送分離 的網(wǎng)建模式 建立起管理信息 系統(tǒng) 采取統(tǒng)一經(jīng)營行為 訪銷程序 批發(fā)價(jià)格和核算形式 微機(jī)聯(lián)網(wǎng)和聯(lián)銷計(jì)酬辦法等六個(gè)統(tǒng)一 規(guī)范網(wǎng)絡(luò)運(yùn)行 大大增強(qiáng)了網(wǎng)絡(luò)的功能和作用 實(shí)現(xiàn)了卷煙銷量和企業(yè)經(jīng)營效益同步增長(zhǎng) 與此同時(shí) 武漢煙草通過加大科技投入和整合人力及物流資源 集并全市 13 個(gè)區(qū)的卷煙倉庫 實(shí) 行一庫式數(shù)字化倉儲(chǔ) 在卷煙銷售上實(shí)行全市統(tǒng)一電話訪銷 集中收集訂單和集中分揀 配送 實(shí)施 的 一庫式 配送模式 使卷煙購銷實(shí)現(xiàn)科學(xué)化 信息化和自動(dòng)化管理 走在了全國同行業(yè)前列 2 2 武煙集團(tuán)煙草配送線路的發(fā)展現(xiàn)狀 1 在卷煙物流配送體系建設(shè)方面 武煙集團(tuán)堅(jiān)持以市場(chǎng)為主體的體制運(yùn)作 不斷優(yōu)化物流業(yè)務(wù) 流程 積極推行一體化配送 不斷降低運(yùn)營總成本 商品采購由市級(jí)公司統(tǒng)一通過電子商務(wù)平臺(tái)完成 6 集中一個(gè)倉庫 由物流配送中心統(tǒng)一分揀到戶 同時(shí) 結(jié)合各地交通 客戶布局等客觀情況 合理設(shè) 置卷煙轉(zhuǎn)送點(diǎn) 由物流中心用箱式貨車將分揀好的卷煙送至轉(zhuǎn)送點(diǎn) 實(shí)行二級(jí)配送 2 全市統(tǒng)一實(shí)行了 一庫制 配送 全市共設(shè)卷煙倉庫 13 個(gè) 總面積達(dá) 6561 平方米 設(shè)立分 庫的單位實(shí)行 一賬兩庫 集中分揀打碼 二級(jí)中轉(zhuǎn) 直送到戶 的方式 對(duì)分庫所在區(qū)營銷部原有 的倉庫 按照分揀到戶的要求進(jìn)行了改造 3 數(shù)字化卷煙配送中心建設(shè)工作情況 武漢市數(shù)字化 一庫式 卷煙配送工程于 2005 年 9 月 竣工 總投資 890 萬元 全市的卷煙倉庫全部集并 實(shí)行 一庫式 數(shù)字化倉儲(chǔ) 卷煙在物流配送中 心集中分揀到戶 并采用 一級(jí)配 一級(jí)送 和 一級(jí)配 二級(jí)送 兩種模式送貨到戶 目前 武漢 市煙草公司物流配送中心倉儲(chǔ)面積 6561 平方米 能滿足 1 6 萬大箱卷煙的儲(chǔ)存需求 出入庫效率為 600 件 小時(shí) 選用電子標(biāo)簽揀選設(shè)備 分揀效率達(dá)到 7000 8000 條 小時(shí) 日分揀量達(dá) 1500 箱左右 配送服務(wù)覆蓋 13 個(gè)區(qū)共 3 6 萬戶零售客戶 2 3 武煙集團(tuán)煙草配送線路的分析 按照湖北省出臺(tái)的網(wǎng)建工作 九個(gè)統(tǒng)一 的工作要求 武煙集團(tuán)圍繞 100 集中訪銷 100 集中 配送 的工作目標(biāo) 努力打造充滿生機(jī)與活力的市場(chǎng)營銷主體 1 統(tǒng)一卷煙分揀 物流配送體系的建設(shè) 各區(qū)配送中心實(shí)現(xiàn)了卷煙分揀 打碼到戶 目前 全市投入使用的半自動(dòng)分揀線共 13 條 全省有 送貨車 212 輛 配送線路 562 條 基本覆蓋全市 各區(qū)按照確定的配送周期做到了定線路 定人員 定車輛 服務(wù)準(zhǔn)時(shí) 2 關(guān)于物流成本 降低存貨成本和商品損耗 通過對(duì)現(xiàn)有倉庫進(jìn)行改造 建設(shè)數(shù)字化倉庫 實(shí)現(xiàn)了存儲(chǔ)量 類別按 儲(chǔ)位管理 盡可能做到按需調(diào)整入庫量 總量庫存可以加大 單品種庫存可根據(jù)銷售隨時(shí)調(diào)整 減少 占用資金 工商協(xié)同 降低整體物流成本 市分公司實(shí)現(xiàn)統(tǒng)一大配送后 改變了過去工業(yè)企業(yè)將卷煙分送到 區(qū)的狀況 工業(yè)企業(yè)根據(jù)各區(qū)公司銷售計(jì)劃 將卷煙整體配送到倉庫 既降低了將卷煙分送到區(qū)的物 流成本 又解決了過去區(qū)級(jí)營銷部少量需求供應(yīng)不及時(shí)的矛盾 明顯體現(xiàn)出統(tǒng)一大配送的綜合效益 因地制宜 優(yōu)化配送線路 降低物流成本 在建設(shè)現(xiàn)代物流的實(shí)踐中 各區(qū)公司采取主干線路直 接配送和偏遠(yuǎn)區(qū)域分支線路二級(jí)配送相結(jié)合的方式 不斷優(yōu)化重組配送線路 減少人員 降低了物流 成本 卷煙配送采取第三方物流送貨 降低物流成本 在大力發(fā)展集中訪銷配送 完善卷煙銷售網(wǎng)絡(luò)的 同時(shí) 武漢市公司靈活運(yùn)用第三方物流所提供的物流配送服務(wù)和先進(jìn)物流技術(shù) 不僅有利于企業(yè)發(fā)展 降低管理成本 而且能有效規(guī)避交通安全管理風(fēng)險(xiǎn) 武漢市公司在物流配送上采取第三方物流的探索 局部來看規(guī)避了一些風(fēng)險(xiǎn)和費(fèi)用 但在第三方物流的選擇上 要通過對(duì)物流企業(yè)的經(jīng)營資質(zhì) 運(yùn)行成 本 特長(zhǎng)資源 服務(wù)水平 4 個(gè)方面評(píng)估 通過招標(biāo)選擇承擔(dān)風(fēng)險(xiǎn)能力強(qiáng) 營運(yùn)手續(xù)完備 內(nèi)部管理規(guī) 范的第三方物流企業(yè) 并簽訂內(nèi)容全面公平 責(zé)任明確的承包合同 在日常管理上 對(duì)第三方物流企 7 業(yè)要提出相關(guān)要求 一是在分公司卷煙配送中心和基層各營銷部辦公地設(shè)立辦公室 處理卷煙中轉(zhuǎn) 送貨運(yùn)輸工作中的協(xié)調(diào)與銜接等有關(guān)事項(xiàng) 避免出現(xiàn)以包代管的現(xiàn)象 二是駕駛員必須符合行業(yè)管理 要求 三是車輛 貨物 司乘人員和第三責(zé)任人保險(xiǎn)缺一不可 保險(xiǎn)種類和保險(xiǎn)額度必須達(dá)到要求 四是頂替車輛和駕駛員應(yīng)符合雙方簽訂的合同規(guī)定要求并承擔(dān)乙方全部的責(zé)任 五是嚴(yán)禁無行為能力 人 限制行為能力人和無承擔(dān)能力人為責(zé)任擔(dān)保人 六是對(duì)雙方共同確定的規(guī)定配送線路 配送承包 車輛車主或公司在承包期內(nèi)無權(quán)私自轉(zhuǎn)讓或變更 七是車輛狀況應(yīng)始終保持良好 引入第三方物流后 產(chǎn)生的效果主要有 一是有利于降低送貨作業(yè)成本 二是有利于降低安全管 理難度和送貨安全風(fēng)險(xiǎn) 三是有利于企業(yè)集中精力抓好內(nèi)部管理 提高市場(chǎng)管理質(zhì)量 四是有利于適 應(yīng)市場(chǎng)和銷售量的變化 動(dòng)態(tài)選擇配送車輛數(shù)量 2 4 武煙集團(tuán)配送線路存在的問題 1 運(yùn)力不能得到充分發(fā)揮 由于武漢市十三區(qū)區(qū)域廣闊 城市交通擁擠 人口密度不均 給全 市整體配送帶來巨大的運(yùn)輸壓力 不同送貨線路之間存在工作量不均衡的情況 有的線路 吃不飽 而有些偏遠(yuǎn)線路送貨任務(wù)繁重 送貨人員和司機(jī)經(jīng)常加班送貨 產(chǎn)生一系列的安全隱患和服務(wù)質(zhì)量問 題 給公司及員工的利益帶來很大的影響 2 車輛調(diào)度安排不合理 由于每條線路上每次零售戶需求分別不同 每次運(yùn)輸線路都是由司機(jī) 憑經(jīng)驗(yàn)選擇路徑行駛 盲目性較大 經(jīng)常走 彎路 遠(yuǎn)路 冤枉路 費(fèi)力費(fèi)時(shí) 3 配送車輛的滿載率低 由于缺乏對(duì)客戶信息的完整收集 導(dǎo)致車輛的配載不均衡 經(jīng)常出現(xiàn) 半車 空等現(xiàn)象 直接的結(jié)果是滿載率低 第第 3 章章 武煙集團(tuán)配送線路路徑優(yōu)化武煙集團(tuán)配送線路路徑優(yōu)化 針對(duì)武煙集團(tuán)配送路線存在的問題 對(duì)其配送線路進(jìn)行科學(xué)地優(yōu)化和整合 對(duì)配送車輛進(jìn)行合理 的調(diào)度 對(duì)線路之間的工作量進(jìn)行科學(xué)的均衡 對(duì)配送線路裝載率進(jìn)一步合理的提高 是武煙集團(tuán)煙 草配送線路優(yōu)化希望達(dá)到的目標(biāo) 3 1 問題提出與描述 1 已知條件 武漢的所有卷煙零售戶的集合 N 為已知 N 0 1 2 n 其中 0 為配送中心 其他為卷煙零售戶所在地 從配送中心出發(fā)的配送線路 經(jīng)過卷煙零售戶所在地之后再返回配送中心 這時(shí) 配送線路所 經(jīng)過的零售戶的順序稱為路線 在配送中心的配送線路的種類 數(shù)量以及每輛車最大裝載能力 W 為已知 8 卷煙零售戶數(shù)為 n 地理位置為已知 且每一個(gè)客戶的卷煙需求量已知 i P i G i R i 1 2 n 每輛車每日最長(zhǎng)送貨時(shí)間為 k T 配送中心到各零售戶點(diǎn)的距離及零售戶之間的距離為 ij d 1 2 1 in 表示配送中心 1 2 0jn ij i 2 目標(biāo) 車輛應(yīng)用臺(tái)數(shù) k 各車行走路徑 使總的距離最少 滿載率較高 用車較少 3 約束條件 配送線路的車載量 如依維柯的車載量為 80 件 五菱之光車載量為 40 件 配送人員的工作時(shí)間 一般不超過 7 個(gè)小時(shí) 地理上相對(duì)集中的零售戶由一輛送貨車進(jìn)行送貨 送貨車輛按照每天的訂單數(shù)量出庫 配送線路盡可能滿載 每天送貨線路的工作線路基本均衡 3 2 解決思路 總體思路 應(yīng)用先分組后路徑算法 Cluster First Route Second Method 即階段一 對(duì)武漢 煙草配送區(qū)域進(jìn)行分組 階段二 求出最優(yōu)線路 具體思路如下 階段一 第一步 根據(jù)配送輻射半徑 確定一級(jí) 二級(jí)和三級(jí)配送的區(qū)域和和配送中心 中轉(zhuǎn)站 對(duì)接點(diǎn) 位置 以及所覆蓋的零售戶 第二步 根據(jù)零售戶經(jīng)營場(chǎng)所的地理環(huán)境 交通情況的不同將其劃入不同的送貨車輛區(qū) 如分 為依維柯車區(qū) 五菱之光車區(qū)等 第三步 采用聚類算法將同一送貨車區(qū)零售網(wǎng)點(diǎn)進(jìn)行劃分或分組 使地理上相對(duì)集中的零售戶處 于同一輛車的配送區(qū)域內(nèi) 階段二 通過求解中國郵遞員問題 求解某一個(gè)配送線路的配送區(qū)域內(nèi)具體的一條卷煙配送路線或次序 通過上述步驟 將 VRP 問題一步細(xì)化 分割 在滿足系統(tǒng)優(yōu)化目標(biāo)的同時(shí) 提高系統(tǒng)運(yùn)行效率 縮短系統(tǒng)運(yùn)行時(shí)間 使方案更加可行 希冀得到一個(gè)近似的可操作的滿意解 9 3 3 具體實(shí)現(xiàn) 3 3 1 聚類算法簡(jiǎn)介 聚類算法是一種新興的多元統(tǒng)計(jì)方法 是當(dāng)代分類學(xué)與多元分析的結(jié)合 聚類分析是將分類對(duì)象 置于一個(gè)多維空間中 按照其空間親疏進(jìn)行分類 通俗地講 聚類分析就是根據(jù)事物彼此不同的屬性 進(jìn)行辨認(rèn) 將具有相似屬性的事物聚為一類 使得同一類事物具有高度的相似性 相似或不相似的度 量基于數(shù)據(jù)對(duì)象的描述的取值來確定的 通常是利用距離進(jìn)行描述 常見的聚類分析方法有 1 切割的聚類方法 代表算法有 K MEANS 算法 ISODATA 算法等 2 層次的聚類方法 代表算法 CURE 算法 3 基于密度的聚類 代表算法 DBSCAN 算法等 4 基于網(wǎng)格的聚類 代表算法 CLIQUE 算法等 煙草行業(yè)配送線路優(yōu)化需要對(duì)零售戶的空間地理數(shù)據(jù)進(jìn)行聚類分析 由于數(shù)據(jù)量較大 需要一個(gè) 效率高的算法 而且 K MEANS 算法適合于數(shù)據(jù)型數(shù)據(jù) 對(duì)數(shù)據(jù)輸入順序不敏感等特點(diǎn) 為比較適合的 一種算法 K MEANS 聚類算法的基本思路是 首先從 n 個(gè)數(shù)據(jù) 8 對(duì)象任意選擇 k 個(gè)對(duì)象作為初始聚類中心 而對(duì)于所剩下其它對(duì)象 則根據(jù)它們與這些聚類中心的相似度 距離 分別將它們分配給與其最相 似的 聚類中心所代表的 聚類 然后再計(jì)算每個(gè)所獲新聚類的聚類中心 該聚類中所有對(duì)象的 均值 不斷重復(fù)這一過程直到所有中心都不在變化為止 k 個(gè)聚類具有以下特點(diǎn) 各聚類本身盡可 能的緊湊 而各聚類之間盡可能的分開 3 3 2K MEANS 聚類實(shí)現(xiàn) K MEANS 聚類算法有兩個(gè)關(guān)鍵問題需要解決 一是初始聚類中心的個(gè)數(shù) 二是初始聚類中心的位 置 1 初始聚類中心的個(gè)數(shù) 也是配送區(qū)域劃分的個(gè)數(shù) 也就是為這些配送區(qū)域送貨的配送線路的 臺(tái)數(shù) 即 k 配送線路的臺(tái)數(shù) 1 加 1 主要考慮車輛配裝時(shí)不可能完全滿載 送貨量 車載量 2 初始聚類中心的位置 原算法是隨機(jī)的 為提高聚類的效果 優(yōu)化聚類的結(jié)果 依照密度的分布 對(duì)初始聚類中心優(yōu)化生成 以每個(gè)零售戶的地理數(shù)據(jù)點(diǎn)為圓心 以數(shù)據(jù)庫中零售戶地理信息表中所有地理數(shù)據(jù)之間距離的平 均值為半徑作圓 然后根據(jù)每個(gè)圓內(nèi)的數(shù)據(jù)點(diǎn)的密度來排序確定初始聚類中心 這樣 k means 聚 類算法需要的初始中心就由以上算法生成 而無需用戶進(jìn)行事先指定 整個(gè)過程包括以下幾個(gè)基本步 驟 1 將數(shù)據(jù)庫中的每個(gè)點(diǎn)都看成一個(gè)類 計(jì)算所有點(diǎn)之間的距離 生成距離矩陣 兩點(diǎn)之間歐式的距 10 離為 22 ij D ijij xxyy 1 2 3 i jn 2 選取 2 個(gè)正數(shù) 一般 R2 2 R1 其中 R1 為數(shù)據(jù)庫中所有點(diǎn)之間距離的平均值 11 nn ij ij D D n n 3 以每個(gè)點(diǎn)為圓心 以 R1 為半徑作圓 計(jì)算落在每個(gè)圓內(nèi)的點(diǎn)數(shù)目 即樣本密度 如求點(diǎn)的樣本密 度的樣本密度 iii A x y i Step1 令 0 i Step2 取判斷其是否落在以以 R1 為半徑的圓內(nèi) 其判斷方法為 111 A x y iii A x y 如上述成立 則 22 111 1 iii A AxxyyR 1ii Step3 判斷是否所有點(diǎn)均已判斷完 如果完畢 即為的樣本密度 否則判斷下一點(diǎn) 重復(fù)第二 i i A 步 4 將樣本密度按從大到小的順序排列 取密度最大者作為第一個(gè)聚類中心 Z1 選擇密 度次大的數(shù)據(jù)點(diǎn) 若與第一凝聚點(diǎn)之間距離大于 R2 即 則把作為第二個(gè) Z Z 1 Z 1 2Z ZR Z 凝聚點(diǎn) Z2 否則繼續(xù)判定下一密度最大者 若下一密度最大者的點(diǎn)與前面若干個(gè)凝聚點(diǎn)之間距離均大 于 R2 則將之作為又一新的凝聚點(diǎn) 如此反復(fù)迭代直到達(dá)到要求聚類的數(shù)目 k 5 把得到的 k 個(gè)聚類中心 Z1 Z2 Z3 Zk 作為 K MEANS 算法的初始聚類中心 我們選取武昌 這一地區(qū)的 97 戶零售商 其分布如下圖 圖圖 1 1 武昌區(qū)煙草零售戶的地理坐標(biāo)信息模擬武昌區(qū)煙草零售戶的地理坐標(biāo)信息模擬 按照上述改進(jìn)后聚類算法的思路 將 97 個(gè)零售戶分成八個(gè)類 即八個(gè)配送區(qū)域 11 圖圖 2 2 八個(gè)類的分布圖 情況二 八個(gè)類的分布圖 情況二 3 3 3 以車載量為限制條件對(duì)聚類結(jié)果調(diào)整 聚類完成后 還應(yīng)根據(jù)車載量這個(gè)約束條件對(duì)聚類結(jié)果進(jìn)行判斷調(diào)整 具體實(shí)現(xiàn)方法為 Step1 計(jì)算每一個(gè)類內(nèi)的零售戶的訂單量總和 Step2 判斷每一類內(nèi)零售戶訂單量總和是否超過車載量如果未超過 說明符合限制條件 如果超過車載量 選擇該類中距離質(zhì)心最遠(yuǎn)的點(diǎn) 將其擬歸入距離其他類質(zhì)心距離最近的類 歸 入某一類前 還必須判斷如歸入后該類的卷煙零售戶的訂單量是否小于車載量 如果小于 即將該數(shù) 據(jù)歸入該類 否則 選擇歐氏距離再次之的類作為擬歸入的類 同樣判斷該類卷煙零售戶訂貨量是否 小于車載量 如果小于則歸 否則選擇距離再次之的 Step3 當(dāng)所有的類零售戶訂單量總和都小于車載量時(shí) 暫告一段落 調(diào)整完畢以后 每一類的卷 煙零售戶地理位置相對(duì)集中 且訂單量總量小于車載重量 3 3 4 以工作量為限制條件對(duì)聚類結(jié)果調(diào)整 提出泛工作量的概念 對(duì)配送線路的工作量進(jìn)行測(cè)量 并以工作量為約束條件對(duì)聚類以后的結(jié)果 進(jìn)行調(diào)整 關(guān)于配送人員工作量的計(jì)算一直是物流配送中心管理工作中一個(gè)難點(diǎn) 難點(diǎn)之一在于影響配送人 員工作量的因素較多 難點(diǎn)之二在于各影響因素的量綱不統(tǒng)一 無法計(jì)算和判斷 為了能更好地計(jì)算配送人員的工作量 筆者通過與配送中心管理人員 駕駛員 送貨員進(jìn)行廣泛 接觸 了解配送人員的實(shí)際工作情況 并通過實(shí)地跟車送貨 提出了一個(gè)衡量配送人員工作量 包括 駕駛員和送貨員 的一個(gè)概念 泛工作量 該指標(biāo)綜合考慮了送貨里程 零售戶戶數(shù) 送貨卷 煙量 以及零售戶的結(jié)算方式 路況等因素 并且通過一定的權(quán)值 將各個(gè)影響因素均統(tǒng)一轉(zhuǎn)化成秒 分或小時(shí)這些時(shí)間單位的數(shù)值 從而將工作量的大小以工作時(shí)間的長(zhǎng)短來表示 能比較直觀和準(zhǔn)確地 衡量不同送貨線路負(fù)荷大小 具體可以用下式來表示 12 234 1 iiiiii La Ca pa Ra HD 上式為配送線路的長(zhǎng)度 該條配送線路上零售戶數(shù) 為該條配送線路上卷煙配送量 i C i P i R 為配送線路上現(xiàn)金結(jié)算的零售戶 D 為配送人員每天配送卷煙必須花費(fèi)的固定時(shí)間 主要包括車況 i H 檢查 停車入庫的時(shí)間 現(xiàn)金交付銀行 分別為 的權(quán)值 該數(shù)值 1 a 2 a 3 a 4 a i C i P i R i H 的確定主要根據(jù)對(duì)歷史數(shù)據(jù)的分析以及根據(jù)筆者的實(shí)地跟車送貨過程對(duì)配送人員具體工作量的分析得 出 1 系數(shù)的確定 影響系數(shù)有兩個(gè)因素 一是配送線路速度理論速度 v 二是配 1 a 1 1 a bv 1 a 送道路的路況 用交通路況系數(shù) b 來表示 路況越差 b 越小 配送時(shí)間越長(zhǎng) 如送貨車輛依維柯行 駛速度為 v 50 公里 小時(shí) 五菱之光行駛速度為 v 30 公里 小時(shí) 如果將路況分三級(jí) 必要時(shí)可以 分得更細(xì) 根據(jù)路況的不同 可以得到不同的 具體見下表 1 a 表表 1 1 系數(shù)結(jié)果系數(shù)結(jié)果 1 a 一級(jí) 政務(wù)區(qū) 二級(jí) 住宅區(qū) 三級(jí) 商業(yè)區(qū) 交通路況系數(shù) 1 b 0 80 60 4 依維柯速度 v40 公里 小時(shí)30 公里 小時(shí)20 公里 小時(shí) 五菱之光速度 v24 公里 小時(shí)18 公里 小時(shí)12 公里 小時(shí) 依維柯 1 a 0 025 0 033 0 05 五菱之光 1 a 0 0420 0560 083 配送線路的長(zhǎng)度 即配送線路將卷煙送到其配送區(qū)域內(nèi)的所有零售戶門上所行駛的線路長(zhǎng)度 它的計(jì) 算是一個(gè)比較復(fù)雜的計(jì)算 將會(huì)在下述中國郵遞員問題中進(jìn)行探討 2 系數(shù)的確定 系數(shù)取決配送人員完成一個(gè)零售戶配送流程的時(shí)間 按照目前的工作規(guī)范 2 a 2 a 和要求 配送人員的工作流程大致為 停車靠邊 搬煙下車 步行到零售戶店中 問候溝通 清點(diǎn)卷煙 粘貼送貨票據(jù) 收取現(xiàn)金 步行回到車上 啟動(dòng)開車 其中清點(diǎn)卷煙的時(shí)間與 該零售戶所訂卷煙數(shù)量有關(guān) 將會(huì)在討論系數(shù)時(shí)加以確定 其他各環(huán)節(jié)所用時(shí)間基本相同 該系數(shù) 3 a 可通過對(duì)歷史數(shù)據(jù)或?qū)嵉卣{(diào)查數(shù)據(jù)的采集分析得到 如根據(jù)實(shí)地調(diào)查 平均每戶零售戶完成這個(gè)規(guī)定 環(huán)節(jié)的工作約需兩分半鐘 即 系數(shù)為 1 8 分鐘 戶 2 a 3 系數(shù)的確定 系數(shù)由配送前裝車時(shí)間和卷煙清點(diǎn)時(shí)間構(gòu)成 每天配送前 配送 3 a 3 a 31 a 32 a 人員將卷煙人員搬運(yùn)上車 所消耗的時(shí)間為裝車時(shí)間 配送人員將卷煙送到零售戶店中 送貨員會(huì)當(dāng) 著零售戶的面 對(duì)卷煙數(shù)量 品種和質(zhì)量以及清點(diǎn)核對(duì) 并請(qǐng)零售戶在送貨單上確認(rèn)簽字 這是卷煙 清點(diǎn)時(shí)間 這是清點(diǎn)時(shí)間 根據(jù)實(shí)地考察 平均每增加五十條卷煙 裝車時(shí)間會(huì)增加 24 秒 即 0 4 31 a 13 分鐘 每件 將增加清點(diǎn)時(shí)間 1 5 分鐘 即清點(diǎn)系統(tǒng)系數(shù)為 1 5 分鐘 件 3 a 0 4 1 5 1 9 32 a 分鐘 件 4 系數(shù)的確定 為向現(xiàn)金結(jié)算戶收取現(xiàn)金的時(shí)間 約為 2 分鐘 戶 以一條送貨線路 4 a 4 a 4 a 為例 該送貨線路送貨車型為依維柯 其 2008 年 11 月送貨數(shù)量 52436 條 送貨零售戶 1625 戶 其中現(xiàn)金結(jié)算戶 487 戶 目前電子結(jié)算戶占零售戶的比率約 70 送貨里程 946 公里 其中一級(jí) 路況 206 公里 二級(jí)路況 510 公里 三級(jí)路況 230 公里 有效工作日 22 天 該送貨線路全月 工作量約為 1234 20193412 5 1992 569744408838 06 147 3 iiiii LaCa pa Ra HD 分鐘小時(shí) 該送貨線路平均每天工作量約為 L 22 147 3 22 6 7 小時(shí) 這與實(shí)際工作情況基本相符 目L 前各送貨線路上的送貨時(shí)間一般為 6 7 小時(shí) 進(jìn)一步印證上述計(jì)算工作量的方法的可行性 通過增加 上述兩個(gè)限制條件 聚類結(jié)果調(diào)整為下圖 圖圖 3 3 調(diào)整后的聚類調(diào)整后的聚類 通過 K MENAS 聚類 再加上車載量和工作量這兩個(gè)限制條件對(duì)聚類結(jié)果進(jìn)行整后 配送區(qū)域劃分 完成 在一個(gè)配送區(qū)域內(nèi)如何求得該配送區(qū)域的最優(yōu)行車路線 使得卷煙送貨車沿著這條行車路線能 將卷煙送到每一個(gè)零售戶手中 而且所走的路程最短 這是一個(gè)求解多點(diǎn)之間的最優(yōu)化路線問題 對(duì)于多點(diǎn)之間的最優(yōu)化路線的計(jì)算有很多方法 其中中國郵遞員問題是解決多點(diǎn)之間的最優(yōu)化路 線比較好的模型之一 中國郵遞員問題解決的是邊遍行問題 求的是歐拉回路 具體到煙草配送實(shí)際 對(duì)于某一個(gè)配送區(qū)域 零售戶的經(jīng)營場(chǎng)所是固定分布在街道上 如果配送線路能以最優(yōu)的路線遍行零 售戶所位處的街道上 即能完成送貨任務(wù) 這是一個(gè)求解歐拉回路的中國郵遞員問題 因此 用中國 14 郵遞員問題模型來求解某一個(gè)配送區(qū)域的最優(yōu)配送線路是比較合適的 用數(shù)學(xué)的語言來描述就是一個(gè)配送區(qū)域內(nèi)的最優(yōu)線路求解問題 如果把配送區(qū)域內(nèi)街道用一條邊 街道的長(zhǎng)度用邊權(quán) w來表示 物流配送中心 街道交叉口用點(diǎn)表示 那么一個(gè)卷 j vv i j vv i 煙配送區(qū)域就構(gòu)成一個(gè)邊權(quán)連通無向圖 配送區(qū)域內(nèi)最優(yōu)線路的問題用圖論的語言來描述 就是在一 個(gè)邊權(quán)連通無向圖中 怎么尋找一個(gè)回路 C 使得 C 至少經(jīng)過每條邊一次且 C 的長(zhǎng)度最短 這里我們選取洪山區(qū)這一聚類 描繪出分布圖 以 A 點(diǎn)為物流配送中心 V1 至 V11 為街道的交 叉口 如下圖所示 圖 4 洪山區(qū)煙草零售商分布圖 15 圖圖 5 5 聚類的模擬圖聚類的模擬圖 如果能尋找一個(gè)回路 C 使得 C 至少經(jīng)過每條邊一次且 C 的長(zhǎng)度最短 C 即是該配送區(qū)域的最 優(yōu)送貨線路 關(guān)于中國郵遞員問題的基本解題在上文已作了具體的描述 對(duì)于一般的邊權(quán)連通無向圖 求解歐拉回路的關(guān)鍵在于就是求奇次點(diǎn)對(duì)最小權(quán)完美匹配 3 3 6 最優(yōu)路線的確定 將求 G 奇次點(diǎn)的最小權(quán)完美匹配問題 可轉(zhuǎn)化為指派問題來解 指派問題是運(yùn)籌學(xué)中一個(gè)基本問題 是指管理部門可能經(jīng)常面臨這樣的問題 有若干項(xiàng)任務(wù)需要 完成 又有若干對(duì)象能夠完成其中每項(xiàng)任務(wù) 由于每個(gè)對(duì)象的特點(diǎn)與能力不同 完成各項(xiàng)任務(wù)的效益 也各不相同 又因任務(wù)性質(zhì)的要求或管理上的需要等緣故 每項(xiàng)任務(wù)只能交給一個(gè)對(duì)象去完成 則應(yīng) 指派哪個(gè)對(duì)象去完成哪項(xiàng)任務(wù) 能夠使完成任務(wù)的總效益最佳 這類問題就稱為指派問題或分配問題 指派問題中 人與任務(wù)之間是一對(duì) 每一對(duì)都有一定的消耗 最終要求解使總消耗為最少的人與任務(wù) 的配對(duì) 同樣 奇次點(diǎn)間也是一對(duì)對(duì)的 每對(duì)間的距離即是消耗 最終要求解的就是使總距離為最少 的奇點(diǎn)對(duì) 效率矩陣就是由奇點(diǎn)對(duì)間的距離組成的 此時(shí)就將此問題轉(zhuǎn)化成求解指派問題 1 找出奇點(diǎn)及奇點(diǎn)數(shù) 設(shè)一般配送區(qū)域線路優(yōu)化問題均可找到對(duì)應(yīng)的無向圖為 G V E 設(shè)圖 G Vn Em 有個(gè)奇點(diǎn) 分別記為 由圖的知識(shí)知 r 為偶數(shù) 在本實(shí)例中 配送區(qū)域?qū)?yīng)的無向圖 12 kkkr vvv 如下 16 圖圖 6 6 配送區(qū)域?qū)?yīng)的無向圖配送區(qū)域?qū)?yīng)的無向圖 表表 2 2 各點(diǎn)對(duì)應(yīng)的度數(shù)值各點(diǎn)對(duì)應(yīng)的度數(shù)值 點(diǎn) V1V2V3V4V5V6V7V8V9V10V11V12A 度數(shù) 3233232334332 選取 8 個(gè)奇點(diǎn) 分別為 為了計(jì)算方便 邊的長(zhǎng)度不是一個(gè)絕對(duì)值 按 1346891112 v v v v v v vv 照一定的比例縮小的整數(shù)值 實(shí)際應(yīng)用進(jìn)行一定比例的放大即可 2 求出各個(gè)奇點(diǎn)的最短距離 利用 Floyd 方法 求出各個(gè)奇頂點(diǎn)與之間的最短距離 同時(shí)將各奇點(diǎn)兩兩之間的最短距離 i v j v 也一并求出 記表示奇點(diǎn)與之間的最短距離 記 F 顯然 F 為對(duì)稱矩陣 本例為 ij f mi v mj v ijr r f 17 這個(gè)矩陣就是指派問題中的效益矩陣 3 找出各個(gè)奇點(diǎn)的兩兩配對(duì)的最優(yōu)匹配方案 設(shè)矩陣其中 為最小指派問題的系數(shù)矩陣 ijr r Cc ij ij fij c ij 解決指派問題的一個(gè)重要的方法是匈牙利法 Hungry 法 這種方法是由匈牙利數(shù)學(xué)家考尼格 Konig 提出的 因此得名匈牙利法 匈牙利算法的理論依據(jù)是根據(jù)考尼格提出并證明了的 兩個(gè)定理 定理 1 設(shè)一個(gè)指派問題的效益矩陣為 若從的第 i 行元素中減去一個(gè)數(shù)cij n cij 從第 j 列中減去一個(gè)常數(shù) 得到一個(gè)新的效益矩陣 1 2 i u im 1 2 j vjn ij b 其中每一元素 則問題的最優(yōu)解也是問題的最優(yōu)解 21 ijijij bcuv ij bcij n 定理 2 若一方陣中的一部分元素為 0 一部分元素為非 0 由覆蓋方陣內(nèi)所有 0 元的最少 直線數(shù)恰好等于那些位于不同行 不同列的 0 的最多個(gè)數(shù) 21 用該法可求出為本例的最優(yōu)解 即 為獨(dú)立的 8 個(gè) 0 元 即最小指派解對(duì)應(yīng)的系數(shù)和為 17233248566571 84 o o o o o o o o 18 1723324856657184 2 1 1 3 1 12314cccccccc 所以為該配送區(qū)域郵路問題的奇點(diǎn)最優(yōu)配對(duì)方案 即選擇 配對(duì) 配對(duì) 17234856 ffff 111 v v 34 v v 配對(duì) 配對(duì) 配對(duì)所得的最小和為 612 v v 89 v v 17234856 7ffff 4 為各個(gè)配送奇點(diǎn)的最短徑加邊 圖圖 6 6 加邊后的最短路經(jīng)加邊后的最短路經(jīng) 在郵路圖中對(duì)每個(gè)配對(duì)奇點(diǎn)之間按照最短路徑添加重復(fù)邊 得到 此圖中已沒有奇點(diǎn) G 5 從配送中心出 A 發(fā) 找出歐拉回路 此 1112434561267 vvvvvvvvvv 89101189 vvvvvvA 回路即為該配送區(qū)域內(nèi)的最短路徑 總路徑為 55 下圖為送貨車的送貨順序圖 19 圖圖 7 7 送貨順序送貨順序 模擬送貨車的實(shí)際送貨路線 從配送中心 A 出發(fā) 給零售戶 90 送貨 到達(dá)路口 給零售戶 89 送貨 到達(dá)路口 給零售 1 v 2 v 戶 87 送貨 到達(dá)路口 給零售戶 84 送貨 到達(dá)路口 給零售戶 85 送貨 到達(dá) 路口 3 v 10 v 1 v 再到路口 給零售戶 83 送貨 到達(dá) 路口 給零售戶 82 送貨 到達(dá)路口 給零售戶 10 v 11 v 12 v 79 送貨 到達(dá) 路口 給零售戶 88 送貨 到達(dá)路口 再到 路口 給零售戶 73 送貨 4 v 3 v 4 v 到達(dá)路口 給零售戶 72 送貨 到達(dá)路口 給零售戶 78 送貨 到達(dá) 路口 再到路口 5 v 6 v 12 v 6 v 給零售戶 76 送貨 到達(dá)路口 給零售戶 77 送貨 到達(dá)路口 給零售戶 81 送貨 到達(dá) 7 v 8 v 路口 給零售戶 86 送貨 到達(dá)路口 再到 路口 給零售戶 80 送貨 到達(dá)路口 再 9 v 10 v 11 v 8 v 到路口 給零售戶 91 送貨 最后回配送中心 完成了對(duì)些配送區(qū)域內(nèi) 18 位卷煙零售戶的送 9 v 貨任務(wù) 總送貨路程 2 5 1 5 1 1 1 3 4 1 1 3 4 3 3 6 3 1 2 1 2 1 1 55 用此方法 可以 求出所有配送區(qū)域內(nèi)所有送貨車輛的最短行駛路線 20 第第 4 章章 總結(jié)與展望總結(jié)與展望 4 1 主要研究工作總結(jié) 綜上所述 本文對(duì)武漢市煙草集團(tuán)煙草配送線路的優(yōu)化問題提出了一個(gè)比較完整的解決方案 該方案具有以下優(yōu)點(diǎn) 首先 實(shí)現(xiàn)了車輛的合理調(diào)度 減少不必要的出車次數(shù) 配送中心每天根據(jù)配送當(dāng)天的訂貨 量以及配送線路的型號(hào)來決定配送線路出動(dòng)的數(shù)目 在 K MEAN 聚類分析中 按照的 1 訂貨量 車載量 方法求出 K 值 K 既是聚集點(diǎn)的個(gè)數(shù) 也是送貨車輛出動(dòng)的數(shù)量 如果按照 30000 箱的年銷售 量 80 件的車載量 11 條配送線路來計(jì)算 平均每天出動(dòng)的配送線路為 輛 全年預(yù)計(jì)可減少出車次數(shù) 30000 250 1 7 47 18 12 20 92 80 50 車次 減少送貨 1506 人次 11 8 20 92 12 753 12 其次 提高車輛滿載率 通過出車次數(shù)的減少 必然提高每輛車的滿載率 如果以每天平均 8 輛的出車數(shù)來計(jì)算 車輛滿載率為 遠(yuǎn)遠(yuǎn)高于現(xiàn)在的配送線 30000 250 93 36 8 12 20 92 80 50 路滿載率 30000 250 67 90 11 12 20 92 80 50 第三 實(shí)現(xiàn)了配送線路送貨線路的最優(yōu)化生成 通過 K MEANS 聚類算法形成配送區(qū)域 再利 用指派問題求解 CPP 問題得到每一個(gè)配送區(qū)域內(nèi)的最優(yōu)線路 使每一輛配送線路能按照優(yōu)化的 配送線路行駛送貨 有效縮短了行車?yán)锍?避免走重復(fù)路 回頭路 同時(shí)為零售戶的送貨服務(wù)更 及時(shí) 該解決方案科學(xué)合理 結(jié)構(gòu)嚴(yán)謹(jǐn) 層層緊扣 通過四步將 VRP 問題層層分解 細(xì)化 減小問 題規(guī)模 得到可行解 一是在配送區(qū)域劃分采用了 K MEANS 方法 并對(duì)初始聚類點(diǎn)的確定方法進(jìn) 行優(yōu)化改進(jìn) 使聚類結(jié)果更加合理 效率更高 二是在配送區(qū)域劃分時(shí)加上工作量和車載量?jī)蓚€(gè) 約束條件 使最終結(jié)果真正有實(shí)用價(jià)值 三是在求解配送區(qū)域內(nèi)的多點(diǎn)最優(yōu)線路問題時(shí) 將其轉(zhuǎn) 化 CPP 問題 通過求解歐拉回路來求解最優(yōu)線路 四是在求解 CPP 問題時(shí)將其轉(zhuǎn)化成指派問題 來求解 總的來說 應(yīng)用上述方法對(duì)武漢煙草集團(tuán)煙草物流配送線路進(jìn)行優(yōu)化 可以科學(xué)地規(guī)劃配送 線路 使線路最優(yōu) 合理地調(diào)度車輛 使?jié)M載率提高 有效地加強(qiáng)內(nèi)部管理 使管理成本降低 對(duì)于實(shí)現(xiàn) 低成本 高效率 優(yōu)服務(wù) 的煙草物流建設(shè)目標(biāo)是一個(gè)很好的推動(dòng) 4 2 未來展望 本論文僅對(duì)物流配送線路優(yōu)化問題進(jìn)行了初步的研究 所獲得的成果還很不完善 還有大量工作 21 需要去做 主要體現(xiàn)在 1 考慮煙草品種的類別 本研究?jī)H考慮客戶需求的貨物重量 并沒有考慮具體的貨物類別 而實(shí) 際上隨著經(jīng)濟(jì)的發(fā)展 消費(fèi)多樣化 要求多樣化 的新觀念逐漸形成 多品種 少批量的配送方式 必