物流配送車輛調(diào)度模型.doc

一般配送費(fèi)用由車輛費(fèi)用、工資費(fèi)用、延遲費(fèi)用和等待費(fèi)用組成。車輛費(fèi)用由燃料費(fèi)、折舊費(fèi)和維修費(fèi)等變動(dòng)費(fèi)用組成，中心根據(jù)經(jīng)營(yíng)情況可核算出每車公里應(yīng)攤的車輛費(fèi)用。工資費(fèi)用根據(jù)途中工作時(shí)間計(jì)算，若工作時(shí)間超過8小時(shí)，則超時(shí)部分應(yīng)按加班補(bǔ)助計(jì)算?？蛻敉ǔＲ筘浳镌谝欢〞r(shí)間窗范圍內(nèi)送達(dá)，否則中心需支付懲罰費(fèi)用。若提前到達(dá)，支付等待費(fèi)用；若延遲到達(dá)，支付延遲費(fèi)用。設(shè)單一配送中心向l個(gè)客戶送貨，第i個(gè)客戶貨運(yùn)量g為，卸貨時(shí)間為，時(shí)間窗為，,每小時(shí)延遲費(fèi)用,中心與客戶、客戶與客戶兩兩間的最短運(yùn)距、平均車速和車輛費(fèi)用分別為(i,j=0,1,2,l;0表示配送中心)；可用m類卡車送貨，第p型卡車有輛，裝載容量為(p=0,1,2,，m)；每小時(shí)等待費(fèi)用為r，行車補(bǔ)助和加班補(bǔ)助分別為每小時(shí)s和es；途中運(yùn)行到中午12：00和下午6：00時(shí)安排30分鐘吃飯時(shí)間，車輛當(dāng)天返回配送中心，再設(shè)為第p類車的第q輛配送的需一求點(diǎn)數(shù)(=0表示未使用第p類車的第q輛車)，確定車輛調(diào)度方案。4.2.2物流配送車輛調(diào)度模型根據(jù)上述對(duì)問題的描述，可以構(gòu)造數(shù)學(xué)模型，定義變量： 得到配送調(diào)度模型如下：目標(biāo)函數(shù)：（4.3） 約束條件： （4.4） （4.5） （4.6） （4.7） （4.8）式中：（4.3）為目標(biāo)函數(shù)，即使車輛在完成配送任務(wù)時(shí)的最小配送費(fèi)用； （4.4）為顧客滿意度約束，即：每一顧客滿意度的平均值必須到80%以上； （4.5）為車輛的能力約束，即：某一車輛所訪問的全部客戶的需求量不能超過車輛本身的載重量； （4.6）確保顧客i僅由第p類車的第q輛車完成配送任務(wù)；(4.7) (4.8) 為到達(dá)某一顧客的車輛唯一性約束，即每一顧客僅由一輛車服務(wù)；其中，表示當(dāng)顧客i的開始時(shí)間為時(shí)，車輛在顧客i處的等待時(shí)間:,j為i的前一個(gè)站點(diǎn)，當(dāng)12且12,或18且18，有；，為發(fā)車時(shí)間，為收車時(shí)間。從模型當(dāng)中可以知道：本文所建的是一個(gè)單目標(biāo)多約束條件的優(yōu)化模型，以配送費(fèi)最小化為目標(biāo)，將車型、車輛裝載量、服務(wù)到達(dá)的時(shí)間要求、午餐時(shí)間及加班費(fèi)等考在內(nèi)，更重要的是通過對(duì)顧客預(yù)約時(shí)間滿意程度的了解，建立顧客平均滿意度約束，使配送中心可以在顧客心中留有好的效應(yīng)，進(jìn)而達(dá)到一種長(zhǎng)期合作的效果，從而給配送中心帶來長(zhǎng)期效益，而不僅僅是一種短期效益。本論文模型的建立將大大的減少由于配送中心不能達(dá)到服務(wù)顧客的要求，而帶來的信譽(yù)損失部分，同時(shí)還提高了企業(yè)的信譽(yù)做到“雙贏”，這是任何一個(gè)企業(yè)或個(gè)人都希望得到的，通過本模型得到的優(yōu)化方案，將更有益于配送中心的發(fā)展。4.3物流配送系統(tǒng)軟硬件基本配置4.3.1物流配送系統(tǒng)的硬件配置在系統(tǒng)編碼之前，為建立開發(fā)和測(cè)試環(huán)境，需要安裝數(shù)據(jù)庫(kù)服務(wù)器、WEB服務(wù)器、應(yīng)用服務(wù)器和其他一些相關(guān)的支撐軟件。1、WEB 服務(wù)器1 臺(tái)。該服務(wù)器可利舊服務(wù)器，即借用現(xiàn)有WEB 服務(wù)器，其功能主要是公司局域網(wǎng)下的頁(yè)面?zhèn)鬏?、用戶的訪問與申請(qǐng)、物流中心車輛調(diào)度員的操作輸入和使用、管理員的維護(hù)等。2、數(shù)據(jù)庫(kù)服務(wù)器（DB服務(wù)器）1臺(tái)。線路優(yōu)化用數(shù)據(jù)庫(kù)主要包括銷售營(yíng)業(yè)部信息數(shù)據(jù)庫(kù)（包括客戶靜態(tài)數(shù)據(jù)和訂貨量動(dòng)態(tài)數(shù)據(jù)），物流中心送貨車輛、駕駛員、送貨員數(shù)據(jù)庫(kù)等。3、應(yīng)用服務(wù)器1臺(tái)。主要用來放置配送線路優(yōu)化應(yīng)用系統(tǒng)，實(shí)現(xiàn)從WEB服務(wù)器傳來的信息和密碼的驗(yàn)證、查詢、獲取、計(jì)算，同時(shí)調(diào)用數(shù)據(jù)庫(kù)服務(wù)器的數(shù)據(jù)資源，進(jìn)行應(yīng)用系統(tǒng)決策模型的分析決策（需要時(shí)修改數(shù)據(jù)庫(kù)服務(wù)器的數(shù)據(jù)）, 最終結(jié)果經(jīng)WEB服務(wù)器反饋給客戶端。4、其它一些網(wǎng)絡(luò)連接器件。如集線器HUB、交換機(jī)等。4.3.2物流配送系統(tǒng)的軟件配置軟件系統(tǒng)應(yīng)參照目前公司所采用的平臺(tái)，如Window 2003 版操作系統(tǒng)，SQLServe2000 以上數(shù)據(jù)庫(kù)系統(tǒng)。1、操作系統(tǒng)。數(shù)據(jù)庫(kù)服務(wù)器和Web 服務(wù)器性能要求比較高，操作系統(tǒng)選用Windows 2003?？蛻舳斯ぷ髡镜牟僮飨到y(tǒng)可選用windows xp /2 000。2、GIS 平臺(tái)選擇。GIS 平臺(tái)軟件應(yīng)考慮到軟件的穩(wěn)定性以及與其它系統(tǒng)集成的問題。根據(jù)前文確定的基于組件開發(fā)模式，選擇MapInfo6.o 以上版本。3、數(shù)據(jù)庫(kù)管理軟件。選擇關(guān)系型數(shù)據(jù)庫(kù)Sql Server 2000的集成來實(shí)現(xiàn)數(shù)據(jù)庫(kù)管理。Sql Server 2000提供海量數(shù)據(jù)存儲(chǔ)，系統(tǒng)運(yùn)行比較穩(wěn)定，相對(duì)于市場(chǎng)上其它同類產(chǎn)品價(jià)格也較適中。4、可視化程序開發(fā)工具。選擇Visual Basic6.0。目前，VB和MO 的結(jié)合被認(rèn)為是開發(fā)GIS 應(yīng)用軟件的最佳選擇之一，VB的程序編寫是可視化的。4.4本章小結(jié)本章以具有代表性的北大倉(cāng)啤酒有限公司的一市多縣物流配送拓?fù)浣Y(jié)構(gòu)為研究對(duì)象，參照實(shí)際工中的約束條件，針對(duì)有時(shí)間窗的車輛路徑的優(yōu)化問題，建立數(shù)學(xué)模型，采用遺傳算法求解。第5章 物流配送優(yōu)化的具體實(shí)現(xiàn)GPS、GIS、車輛調(diào)度的功能集成主要是根據(jù)北大倉(cāng)啤酒有限公司物流配送需要，通過GPS實(shí)現(xiàn)車輛管理及數(shù)據(jù)采集功能，GIS實(shí)現(xiàn)電子地圖顯示功能和分析決策功能。5.1物流配送GPS功能實(shí)現(xiàn)5.1.1GPS系統(tǒng)總體架構(gòu)本系統(tǒng)利用車輛終端設(shè)備GPS接收模塊接收GPS衛(wèi)星信號(hào)，經(jīng)過解算后得到車輛的動(dòng)態(tài)位置，車輛終端設(shè)備的GPRS 模塊將帶有車輛位置信息通過中國(guó)移動(dòng)網(wǎng)關(guān)發(fā)送到監(jiān)控中心，監(jiān)控中心接收到車輛終端發(fā)送來的信息，經(jīng)解算后在監(jiān)控中心的電子地圖上顯示車輛的動(dòng)態(tài)位置及行車路線，監(jiān)控中心可利用GSM通訊網(wǎng)向車輛司機(jī)發(fā)送語(yǔ)音短信等調(diào)度指示45。車載終端設(shè)備中國(guó)移動(dòng)網(wǎng)關(guān)GPS天線GPS天線基站.GPS衛(wèi)星定位系統(tǒng)公司中各業(yè)務(wù)部門GPS系統(tǒng)運(yùn)輸線路優(yōu)化系統(tǒng)公司中各業(yè)務(wù)部門優(yōu)化系統(tǒng)GIS衛(wèi)星定位系統(tǒng)公司中各業(yè)務(wù)部門GIS系統(tǒng) 圖5-1 GPS框架圖Chart 5-1 GPS frame chart5.1.2 GPS 監(jiān)控中心設(shè)置利用己經(jīng)建設(shè)成的局域網(wǎng)，在其信息中心機(jī)房設(shè)置服務(wù)器、交換機(jī)等硬件設(shè)備和相應(yīng)系統(tǒng)管理和維護(hù)人員，在各管理職能部門或者各業(yè)務(wù)部門可以建立分監(jiān)控中心，以網(wǎng)絡(luò)終端與服務(wù)器相連來操作和應(yīng)用系統(tǒng)。監(jiān)控中心是整個(gè)系統(tǒng)的核心，是連接分中心與車輛移動(dòng)終端的紐帶，并對(duì)分中心和車輛進(jìn)行數(shù)據(jù)管理和通信，事實(shí)上分中心只與總監(jiān)控中心進(jìn)行數(shù)據(jù)通信，而車輛終端也只和總監(jiān)控中心通訊。5.1.3 GPS 系統(tǒng)功能設(shè)計(jì)（1）實(shí)時(shí)監(jiān)控：監(jiān)控中心可隨時(shí)查詢或跟蹤所有配送中心車輛所在的當(dāng)前位置，同時(shí)顯示出車速，經(jīng)緯度，車狀態(tài)，司機(jī)及乘員等信息，對(duì)的車輛行蹤了如指掌。電子地圖可任意放大、縮小、移動(dòng)，可多窗口顯示、分別顯示不同的地址區(qū)域、一個(gè)窗口可同時(shí)跟蹤多個(gè)目標(biāo)、將目標(biāo)鎖定在某窗口自動(dòng)漫游跟蹤、固定區(qū)域內(nèi)的監(jiān)控、多個(gè)窗口跟蹤多個(gè)目標(biāo)以及可在不同的窗口顯示不同的目標(biāo)，或?qū)⒛繕?biāo)鎖定在某窗口，自動(dòng)跟蹤等。（2）地圖及GIS 軟件功能：（需要采集零售戶經(jīng)維度數(shù)據(jù)）完全數(shù)字化的地圖，包含精確的路網(wǎng)信息、點(diǎn)狀要素、面狀要素和詳細(xì)的屬性信息。作為北大倉(cāng)物流公司車輛監(jiān)控平臺(tái)的支撐，地圖的無級(jí)放大、縮小、恢復(fù)和拖動(dòng)。全城市地圖與各城區(qū)地圖之間的任意轉(zhuǎn)換，每圖各層之間的轉(zhuǎn)換，地名模糊查詢，零售戶查詢等，管理功能強(qiáng)大，操作及為方便。（3）鷹眼窗口：在進(jìn)行車輛監(jiān)控時(shí)，顯示當(dāng)前窗口在全圖中的位置，當(dāng)前窗口圖變化時(shí)，鷹眼窗口自動(dòng)進(jìn)行相應(yīng)變化。鷹眼窗口地圖本身也可放大縮小、漫游。通過改變鷹眼窗口位置框的尺寸和位置可改變相應(yīng)的窗口地圖顯示區(qū)域。這樣有利于監(jiān)控中心更清楚的了解目前車輛的即時(shí)位置。（4）區(qū)域查詢：為禁止公司車輛的隨意跑崗，可對(duì)每一輛車劃定送配區(qū)域。監(jiān)控中心可以隨時(shí)查詢車輛的當(dāng)時(shí)位置；當(dāng)車輛跑處行駛區(qū)域時(shí)，即可對(duì)監(jiān)控中心及時(shí)進(jìn)行報(bào)警提示。技術(shù)實(shí)現(xiàn)方法是：中心把相應(yīng)的查車區(qū)域參數(shù)通過廣播（小區(qū)消息）向所有網(wǎng)內(nèi)車輛發(fā)送，移動(dòng)終端接收到此指令后，判斷是否處在此區(qū)域，如果是在此區(qū)域，就立刻向中心反饋當(dāng)前的位置和狀態(tài)信息。（5）歷史資料檢索與歷史軌跡回放：可隨時(shí)查詢某輛車的位置回報(bào)記錄、某段時(shí)間接收的車輛位置回報(bào)信息、某段時(shí)間監(jiān)控中心的車輛調(diào)度記錄等詳細(xì)記錄。并可選定某輛車某時(shí)間段的位置記錄進(jìn)行軌跡回放，便于考核和管理。（6）車輛檔案管理：數(shù)據(jù)庫(kù)錄有車輛及司機(jī)的詳細(xì)資料，包括維修記錄等，能自動(dòng)提醒車輛及時(shí)檢修；利于公司對(duì)車輛的管理。（7）超速報(bào)警、超載報(bào)警處理：為保障送配人員以及公司車輛的安全，要避免駕駛?cè)藛T超速駕駛。監(jiān)控中心自動(dòng)接受車輛的報(bào)警信號(hào)，在地圖上將對(duì)該目標(biāo)進(jìn)行鮮明色彩及圖標(biāo)的突出顯示并以聲、光報(bào)警提醒值班員注意，同時(shí)在屏幕上顯示該移動(dòng)目標(biāo)的用戶卡片資料，如車輛編號(hào)、車牌號(hào)、車型、顏色及司機(jī)名等；具有報(bào)警確認(rèn)、報(bào)警取消、遙控熄火、遙控恢復(fù)、分發(fā)報(bào)警、指定路線報(bào)警、超速報(bào)警、后車廂開報(bào)警、車門開報(bào)警等輔助決策功能。（8）異常狀態(tài)處理：車輛異常狀態(tài)的帶車號(hào)列表顯示。異常狀態(tài)包括：緊急求助、服務(wù)申請(qǐng)、醫(yī)療服務(wù)申請(qǐng)、公交車輛故障報(bào)告、異常入侵等。（9）緊急求助：監(jiān)控中心可以設(shè)置車輛的最高時(shí)速。隨著大配送后，隨車人員的貨物與現(xiàn)金的增加，要避免搶劫等意外情況。在目標(biāo)遇到突發(fā)事件以及偷竊等情況時(shí)，其向中心發(fā)回緊急求助信號(hào)，在地圖上將對(duì)該目標(biāo)進(jìn)行鮮明色彩及圖標(biāo)的突出顯示并以聲、光報(bào)警提醒值班員注意，同時(shí)在屏幕上顯示出該移動(dòng)目標(biāo)的用戶卡片資料，它包括車輛編號(hào)、車牌號(hào)、車型、顏色、發(fā)動(dòng)機(jī)號(hào)、使用分類、司機(jī)名、駕駛證號(hào)、所屬單位、負(fù)責(zé)人、電話、車輛位置（X , Y 坐標(biāo)）、行駛速度、時(shí)間等信息，幫助值班員進(jìn)行緊急處理。軟件能提供緊急求助受理記錄窗，供值班員記錄受理情況。5.2物流配送GIS功能實(shí)現(xiàn)5.2.1MapInfo應(yīng)用Maplnfo 是美國(guó)MapInfo 公司的產(chǎn)品46-48。MapInfo Professional 是近兩年來推出的主流地理信息系統(tǒng)產(chǎn)品，它吸取了傳統(tǒng)GIS系統(tǒng)的精華，并借助于計(jì)算機(jī)技術(shù)的發(fā)展，及時(shí)地將GIS 的概念從大中型計(jì)算機(jī)的專用工作站引入到普通PC 機(jī)上，開創(chuàng)了一種嶄新的地理信息系統(tǒng)模式，即桌面地理信息系統(tǒng)。MapInfo的推出吸引了越來越多的用戶。該產(chǎn)品自90 年代初進(jìn)入我國(guó)后，在各行各業(yè)得到普遍的應(yīng)用，并收到良好的應(yīng)用效果。用VB編寫的客戶端應(yīng)用程序MapInfo Professional服務(wù)程序MapInfo數(shù)據(jù)維護(hù)MapInfo數(shù)據(jù)維護(hù)OLE或者DDE物流信息數(shù)據(jù)庫(kù)GIS空間數(shù)據(jù)庫(kù)圖5-2 MapInfo 在物流配送系統(tǒng)的應(yīng)用Chart 5-2 MapInfo logistics delivers the system in the thing the applicationMapInfo 的主要開發(fā)過程有：（1）輸入。在地理數(shù)據(jù)用于GIS 之前，數(shù)據(jù)必須轉(zhuǎn)換成適當(dāng)?shù)臄?shù)字格式。從圖紙數(shù)據(jù)轉(zhuǎn)換成計(jì)算機(jī)文件的過程叫做數(shù)字化。對(duì)于大型的項(xiàng)目，現(xiàn)代GIS 技術(shù)可以通過掃描技術(shù)來使這個(gè)過程全部自動(dòng)化，對(duì)于較小的項(xiàng)目，需要手工數(shù)字化（使用數(shù)字化桌）。目前，許多地理數(shù)據(jù)已經(jīng)是GIS 兼容的數(shù)據(jù)格式。這些數(shù)據(jù)可以從數(shù)據(jù)提供商那里獲得并直接裝入GIS 中。（2）處理。對(duì)于一個(gè)特殊的GIS 項(xiàng)目來說，有可能需要將數(shù)據(jù)轉(zhuǎn)換成或處理成某種形式以適應(yīng)你的系統(tǒng)。例如，地理信息適用于不同的比例尺(街道中心線文件的比例尺也許是1:100,000；人口邊界是1:50,000)。在這些信息被集成以前，必須轉(zhuǎn)變成同一比例尺。這可以是為了顯示的目的而做的臨時(shí)變換，也可以是為了分析所做的永久變換。（3）管理。對(duì)于小的GIS 項(xiàng)目，把地理信息存儲(chǔ)成簡(jiǎn)單的文件就足夠了。但是，當(dāng)數(shù)據(jù)量很大而且數(shù)據(jù)用戶數(shù)很多時(shí)，最好使用一個(gè)數(shù)據(jù)庫(kù)管理系統(tǒng)(DBMS)，來幫助存儲(chǔ)、組織和管理數(shù)據(jù)。一個(gè)數(shù)據(jù)庫(kù)管理系統(tǒng)DBMS 就是用來管理一個(gè)數(shù)據(jù)庫(kù)（4）查詢和分析。一旦你擁有一個(gè)包含你的地理信息的多功能的GIS 系統(tǒng)，你可能開始提出向下面這樣的一些簡(jiǎn)單問題：兩個(gè)地方之間的距離是多少？工業(yè)用地的邊界在哪里？（5）可視化。對(duì)于許多類型的地理操作，最終結(jié)果最好是以地圖或圖形來顯示。地圖顯示可以集成在報(bào)告、三維觀察、照片圖像和例如多媒體的其他輸出中。5.2.2數(shù)據(jù)準(zhǔn)備及處理 地理信息系統(tǒng)的數(shù)據(jù)來源（數(shù)據(jù)源）是指建立地理信息系統(tǒng)所需的各種類型數(shù)據(jù)的來源，可以分為圖形（地圖）數(shù)據(jù)源和屬性數(shù)據(jù)源49。圖形數(shù)據(jù)源包括地圖、測(cè)繪和遙感影像等；而屬性數(shù)據(jù)源則包括統(tǒng)計(jì)數(shù)據(jù)、各種文字報(bào)告和立法文件、聲音和圖片等。（1）電子地圖設(shè)計(jì)物流GIS 系統(tǒng)的需求決定了電子地圖的內(nèi)容。毫無疑問道路網(wǎng)絡(luò)應(yīng)是本系統(tǒng)最重要的組成部分，其次是送貨點(diǎn)分布信息，同時(shí)也應(yīng)包含與車輛行駛相關(guān)的各類標(biāo)志，除此之外，電子地圖還應(yīng)該包含與企業(yè)相關(guān)的出行、商務(wù)等非道路信息。下面重點(diǎn)討論道路網(wǎng)絡(luò)、送貨點(diǎn)分布信息的具體內(nèi)容 道路網(wǎng)絡(luò)。道路網(wǎng)絡(luò)是整個(gè)電子地圖的基礎(chǔ)，同時(shí)也是許多算法，最短路徑算法、優(yōu)化路徑算法、地圖匹配算法的數(shù)據(jù)來源，尤其是將這些算法作用于電子地圖時(shí)，道路網(wǎng)絡(luò)的設(shè)計(jì)顯得更加重要。道路網(wǎng)絡(luò)包含道路的物理屬性，如一般道路、橋梁等。對(duì)于物流系統(tǒng)來說，還需要知道道路的屬性數(shù)據(jù)，如道路等級(jí)、速度限制、通行車輛種類等。為了更接近實(shí)際道路情況，道路網(wǎng)絡(luò)還應(yīng)該包含道路的行駛屬性，如單行道雙行道、禁止通行等信息。 送貨點(diǎn)分布信息。送貨點(diǎn)信息作為特殊信息，是物流GIS 系統(tǒng)中必不可少的重要內(nèi)容，它是進(jìn)行車輛調(diào)度的基礎(chǔ)信息。一般而言，送貨點(diǎn)信息必須包括可唯一判斷其存在的地理屬性（如常用的所處街道名稱或坐標(biāo)信息），除此之外，還應(yīng)包含別的一些屬性，如：送貨點(diǎn)自身屬性、送貨點(diǎn)相關(guān)屬性等信息。通常，如果送貨點(diǎn)信息是己知的，可提前建立好它的數(shù)據(jù)，也可以在系統(tǒng)使用中間，隨時(shí)添加、刪除或修改送貨點(diǎn)信息。依據(jù)上述電子地圖需求和內(nèi)容分析，進(jìn)行電子地圖設(shè)計(jì)。(2)拓?fù)浣Y(jié)構(gòu)設(shè)計(jì)?？臻g數(shù)據(jù)的拓?fù)潢P(guān)系模型是地理信息系統(tǒng)的基石。本文主要采用“空間實(shí)體十空間索引”的拓?fù)潢P(guān)系模型。“空間實(shí)體空間索引”模型的基礎(chǔ)是“空間實(shí)體”。空間實(shí)體是地理實(shí)體的抽象，主要包括點(diǎn)、線、面三種類型。每個(gè)空間實(shí)體對(duì)象都維護(hù)著自己的所有屬性。多個(gè)空間實(shí)體組成一個(gè)圖層。“空間實(shí)體十空間索引”模型的空間查詢功能是通過“空間索引”技術(shù)來實(shí)現(xiàn)的。5.2.3GIS實(shí)現(xiàn)的主要功能1、圖層控制功能：用戶可以在地圖上方便設(shè)置地圖圖層的可見、顯示標(biāo)注、可選擇等。2、圖漫游功能：用戶可以方便地在地圖上進(jìn)行放大、縮小、移動(dòng)電子地圖。3、零售戶搜索功能：用戶可以采取單一選擇、矩形選擇、圓型選擇的方式搜索一定區(qū)域內(nèi)的零售戶對(duì)象并且對(duì)這些對(duì)象的信息進(jìn)行統(tǒng)計(jì)、分析。4、數(shù)據(jù)分析功能： 客戶基本信息； 銷售量、銷售額分析； 毛利分析； 客戶獲利分析； 卷煙銷售結(jié)構(gòu)分析； 銷售數(shù)據(jù)分布分析； 品牌銷售分布分析；其它應(yīng)用功能的數(shù)據(jù)挖掘和分析。5.3物流配送車輛調(diào)度和優(yōu)化功能實(shí)現(xiàn)5.3.1物流配送系統(tǒng)的流程設(shè)計(jì)本文研究的北大倉(cāng)啤酒有限公司物流配送系統(tǒng)的優(yōu)化問題，而且主要研究多點(diǎn)、小批量、有時(shí)間窗約束的配送問題。根據(jù)配送系統(tǒng)的特征，工作流程設(shè)計(jì)如下：（1）根據(jù)現(xiàn)有設(shè)施點(diǎn)的位置，綜合考慮配送半徑，配送量，對(duì)客戶進(jìn)行分區(qū)處理，將復(fù)雜的優(yōu)化問題簡(jiǎn)化。（2）將呼叫中心收集到的訂單信息輸入系統(tǒng)，經(jīng)過有效性檢驗(yàn)合格后傳遞到配送網(wǎng)絡(luò)子系統(tǒng)；（3）選擇“配送車輛安排模塊”檢驗(yàn)傳遞過來的數(shù)據(jù)并進(jìn)行計(jì)算，確定需多少車輛負(fù)責(zé)配送哪些客戶；（4）將結(jié)果傳遞到“車輛路線安排算法模塊”。調(diào)用GIS子系統(tǒng)，獲取客戶之間距離信息，根據(jù)道路情況計(jì)算配送路程時(shí)間，在客戶停留時(shí)間按照配送量統(tǒng)一計(jì)算（初次實(shí)行人工配合修正）。該模塊針對(duì)各區(qū)域每部車輛，規(guī)劃各自的配送路線；（5）最后進(jìn)行配送方案的評(píng)價(jià)。如果滿意，則進(jìn)入地圖顯示子系統(tǒng)，將結(jié)果以文字的方式在窗口顯示，然在電子地圖上進(jìn)行路線顯示并保存方案。若不滿意，則返回配送網(wǎng)絡(luò)子系統(tǒng)，按如上步驟重新求解。主要工作流程圖如圖所示。GPS、掃描等數(shù)據(jù)采集數(shù)據(jù)庫(kù)GIS空間數(shù)據(jù)物流信息數(shù)據(jù)數(shù)據(jù)接口空間數(shù)據(jù)分析GIS顯示配送車輛調(diào)度配送線路設(shè)計(jì)車輛管理客戶信息可視配送網(wǎng)絡(luò)建立配送方案實(shí)施配送方案評(píng)價(jià)圖 5-3 GPS、GIS、車輛調(diào)度的主要工作流程圖Chart 5-3 GPS, GIS, the vehicles dispatch main work flow chart5.3.2物流配送系統(tǒng)的功能設(shè)計(jì)GIS 子系統(tǒng)物流配送優(yōu)化子系統(tǒng)客戶、空間信息查詢電子地圖顯示GIS統(tǒng)計(jì)分析配送車輛調(diào)度配送路線設(shè)計(jì)GPS子系統(tǒng)車輛管理人員管理物流信息管理子系統(tǒng)倉(cāng)儲(chǔ)管理信息接口訂單信息接口客戶關(guān)系信息接口物流配送系統(tǒng)根據(jù)系統(tǒng)設(shè)計(jì)的基本思路和框架結(jié)構(gòu)，主要包括電子地圖、決策分析、車輛監(jiān)控三個(gè)子系統(tǒng)，其中電子地圖子系統(tǒng)包括電子地圖顯示和空間信息查詢等模塊，決策分析子系統(tǒng)包括GIS 統(tǒng)計(jì)分析、配送區(qū)域劃分、配送車輛安排和配送路線設(shè)計(jì)等功能模塊。主要模塊如圖：圖5-4 車輛調(diào)度主要功能模塊圖Chart 5-4 vehicles dispatcher main function module chart 車輛調(diào)度模塊主要的作用：1、通過GPS 實(shí)現(xiàn)車輛安全保障及監(jiān)控。2、根據(jù)每天不同的訂貨需求，配送車輛盡量裝滿配送貨物，這樣動(dòng)態(tài)生成線路，也就是在同樣完成配送任務(wù)的前提下每天派出的車輛盡量的少，工作時(shí)間盡量短的工作時(shí)間。3、根據(jù)生成的不同線路，給出車輛行駛的最優(yōu)路徑，使得配送同樣的零售點(diǎn)所用的時(shí)間最短，里程油耗及車輛損耗最少。4、路徑分配考慮周全，符合現(xiàn)場(chǎng)實(shí)際情況：比如工作量分配系統(tǒng)要求總成本最低而各條線工作平衡，即不強(qiáng)調(diào)每條線路工作量平衡的平均主義，因?yàn)槿绻菢影才排渌头桨傅脑?，必將使總體工作量增加。所以，我們動(dòng)態(tài)分配線路時(shí)各條線路的工作量允許不同，只要在8 小時(shí)工作時(shí)間范圍內(nèi)，有的線路工作量比其他線路大很多，但這樣多條線路相加，總和必須是繞行里程和時(shí)間最短，同時(shí)又完成了任務(wù)，為單位最大限度地降低了配送成本；為了解決司機(jī)間工作量平衡的問題。我們?cè)O(shè)計(jì)在工作排班制度上，每周輪換跑最遠(yuǎn)的路線。在最優(yōu)路徑的生成中，我們綜合考慮了道路等級(jí)、不同方向和時(shí)段的交通阻抗、交叉口左、右、直行以及不同時(shí)段的時(shí)間延誤、路段是否允許中途掉頭和是否可以過街送貨等情況。5、運(yùn)行效率高，生成結(jié)果準(zhǔn)確合理。系統(tǒng)采用了當(dāng)今高效合理的數(shù)學(xué)模型：遺傳算法與神經(jīng)網(wǎng)絡(luò)算法。兩種方法結(jié)合使用，運(yùn)算速度大大提高。6、生成每條線路，在電子地圖線路上標(biāo)注線路行駛的順序號(hào)并打印成圖，方便司機(jī)工作。同時(shí)，還為每條線路的司機(jī)按行駛順序打印出清單。7、建立客戶信息及數(shù)據(jù)分析可視化功能。有利于經(jīng)營(yíng)管理人員直觀掌握客戶有關(guān)情況，為服務(wù)拓展提供基礎(chǔ)。如客戶投訴，能及時(shí)顯示客戶位置及基本情況，計(jì)算服務(wù)響應(yīng)時(shí)間，以便最有效地實(shí)施服務(wù)補(bǔ)救。5.4車輛調(diào)度遺傳算法的求解5.4.1遺傳算法的運(yùn)行步驟遺傳算法在整個(gè)進(jìn)化過程中的遺傳操作是隨機(jī)的但它所呈現(xiàn)出的特性并不是完全隨機(jī)搜索，它能有效地利用歷史信息來推測(cè)下一代期望性能有所提高的最優(yōu)點(diǎn)集。這樣一代代地不斷進(jìn)化，最后收斂到一個(gè)最適應(yīng)環(huán)境的個(gè)體上，求得問題的最優(yōu)解。遺傳算法的運(yùn)行為一個(gè)典型的迭代過程，其基本執(zhí)行過程如下：（1）編碼：遺傳算法在進(jìn)行搜索之前先將解集合的解的數(shù)據(jù)表示成遺傳空間的基因型串?dāng)?shù)據(jù)，這些串結(jié)構(gòu)的不同組合便構(gòu)成了不同的點(diǎn)。（2）初始群體的生成:隨機(jī)產(chǎn)生N個(gè)初始串結(jié)構(gòu)，每個(gè)串結(jié)構(gòu)稱為一個(gè)個(gè)體(或叫染色體)，N個(gè)個(gè)體構(gòu)成了一個(gè)群體，群體內(nèi)個(gè)體的數(shù)量N就是群體規(guī)模。群體內(nèi)每個(gè)染色體必須以某種編碼形式表示，編碼的內(nèi)容可以表示染色體的某些特征。隨著求解問題的不同，它所表示的內(nèi)容也是不同。通常染色體表示被優(yōu)化的參數(shù)，每個(gè)初始個(gè)體就表示著問題的初始解。（3）適應(yīng)值評(píng)估檢測(cè):適應(yīng)值函數(shù)表明個(gè)體或解的優(yōu)劣性。對(duì)于不同的問題，適應(yīng)值函數(shù)定義的方式也不同。（4）選擇：從當(dāng)前群體中選擇適應(yīng)值高的個(gè)體以生成交配池的過程，其目的是為了從當(dāng)前群體中選出優(yōu)良的個(gè)體，使它們有機(jī)會(huì)作為父代為下一代繁殖子孫。按照一定的選擇策略選擇合適的個(gè)體，選擇實(shí)現(xiàn)了達(dá)爾文的適者生存原則。根據(jù)群體中每個(gè)個(gè)體的適應(yīng)值，從中選擇具有最好的個(gè)體作為父代重新繁殖下一代群體。（5）交叉:交叉是兩個(gè)染色體之間隨機(jī)交換信息的一種機(jī)制。以事先給定的交叉概率在選擇出的個(gè)體中任意選擇兩個(gè)個(gè)體進(jìn)行交叉運(yùn)算或重組運(yùn)算，產(chǎn)生兩個(gè)新的個(gè)體，重復(fù)此過程直到所有要求交叉的個(gè)體交叉完畢。交叉操作是GA中最主要的遺傳操作。通過交叉操作可以得到新一代個(gè)體，新個(gè)體結(jié)合了其父輩個(gè)體的特性。交叉體現(xiàn)了信息交換的思想。（6）變異：變異操作是模擬自然界生物進(jìn)化中染色體上某位基因發(fā)生的突變現(xiàn)象，從而改變?nèi)旧w的結(jié)構(gòu)和物理性狀。它首先在群體中隨機(jī)選擇一個(gè)個(gè)體，對(duì)于選中的個(gè)體以一定的概率隨機(jī)的改變串結(jié)構(gòu)數(shù)據(jù)中某個(gè)串的值。同生物界一樣，GA中發(fā)生變異的概率很低，通常取值在0.0010.01之間。變異為新個(gè)體的產(chǎn)生提供了機(jī)會(huì)。根據(jù)需要可以以事先給定的變異概率，在最好的個(gè)體中選擇若干個(gè)體，并按一定的策略對(duì)選中的個(gè)體進(jìn)行變異運(yùn)算。變異運(yùn)算增加了GA找到最優(yōu)解的能力。(7)終止循環(huán)條件，若滿足收斂條件或固定迭代次數(shù)則終止，若不滿足條件則轉(zhuǎn)(3)重新進(jìn)行進(jìn)化過程。每一次進(jìn)化過程就產(chǎn)生新一代的群體。群體內(nèi)個(gè)體所表示的解通過進(jìn)化最終達(dá)到最優(yōu)解。5.4.2遺傳算法的參數(shù)設(shè)置的選擇遺傳算法中需要選擇的運(yùn)行參數(shù)主要有群體規(guī)模N、迭代次數(shù)、交叉概率、變異概率、終止代數(shù)T等。這些運(yùn)行參數(shù)對(duì)遺傳算法運(yùn)行的性能有著較大的影響，需要認(rèn)真選取。（1）群體規(guī)模N。群體規(guī)模表示群體所含個(gè)體的數(shù)量。當(dāng)取值較小時(shí)，可以提高遺傳算法的運(yùn)算速度，但會(huì)降低群體的多樣性，有可能引起算法的早熟現(xiàn)象；而當(dāng)N較大時(shí)，又會(huì)使得遺傳算法的運(yùn)行效率降低。一般建議取值范圍是20100。（2）迭代次數(shù)。迭代次數(shù)的設(shè)置分為固定和不固定兩種設(shè)置。固定迭代次數(shù)有利于遺傳算法的處理，但設(shè)置選擇困難，并且不利于產(chǎn)生最優(yōu)解。不固定迭代次數(shù)通過對(duì)個(gè)體解的判斷自動(dòng)進(jìn)行迭代有利于產(chǎn)生最優(yōu)解，并且解決了參數(shù)選擇的困難，但容易增加遺傳算法的處理時(shí)間。（3）交叉概率和變異概率。對(duì)交叉概率和變異概率的設(shè)置，由于它們關(guān)系到遺傳算法的收斂性和群體中個(gè)體的多樣性，因此倍受重視。傳統(tǒng)的和的設(shè)置是靜態(tài)人工設(shè)置。現(xiàn)在有學(xué)者提出動(dòng)態(tài)參數(shù)設(shè)置的方法，以減少人工選擇參數(shù)的困難和盲目性，來維持群體的多樣性和保證遺傳算法的收斂。由于交叉算子是產(chǎn)生新個(gè)體的主要方法，所以一般交叉概率取值較大。但若取的過大，又會(huì)破壞群體中的優(yōu)良模式，對(duì)進(jìn)化計(jì)算反而產(chǎn)生不良的影響。一般建議的取值范圍是0.40.99。另外，也可以使用自適應(yīng)的思想來確定交叉概率，隨著遺傳算法在線能的大大提高，以加大交叉概率的取值。變異概率取值較大時(shí)，雖然能夠產(chǎn)生較多的新個(gè)體，但也有破壞很多較好模式的可能，使得遺傳算法的性能近似于隨機(jī)搜索算法的性能但若其取值太小，則變異操作產(chǎn)生新個(gè)體和抑制早熟的能力就會(huì)較差。一般建議其取值范圍是0.0010.01。另外，也可以使用自適應(yīng)的思想來確定，隨著遺傳算法在線性能的下降，可以減小的取值。（4）終止代數(shù)T。終止代數(shù)T是表示遺傳算法結(jié)束的一個(gè)參數(shù)，遺傳算法運(yùn)行到指定的代數(shù)T就停止運(yùn)行，并將當(dāng)前群體中的最佳個(gè)體作為所求問題的最優(yōu)解輸出。一般建議的取值范圍為1001000。另外，遺傳算法的終止條件，還可以利用某種判斷準(zhǔn)則，當(dāng)判斷出群體已經(jīng)進(jìn)化成熟且不再有進(jìn)化趨勢(shì)時(shí)就可終止算法的運(yùn)行。常見判斷準(zhǔn)則有：連續(xù)幾代個(gè)體平均適應(yīng)度的差異小于某個(gè)極小的閥值；或群體中所有個(gè)體適應(yīng)度的方差小于某一個(gè)極小的閥值。5.4.3遺傳算子（1）選擇算子。模仿自然界的“優(yōu)勝劣汰”選擇操作用來確定如何從父代群體中按某種方法選取哪些個(gè)體遺傳到下一代群體的一種遺傳運(yùn)算，也就是從當(dāng)前群體中選擇適應(yīng)值高的個(gè)體以生成交配池的過程。選擇操作建立在對(duì)個(gè)體的適應(yīng)度進(jìn)行評(píng)價(jià)的基礎(chǔ)之上，需要指出的是，選擇算子只是從當(dāng)前群體中選擇較好的個(gè)體形成交配池，本身并沒有產(chǎn)生新的個(gè)體目的主要是為了避免群體中有效基因缺失或成熟前收斂，以及為了GA提高的全局收斂性和搜索效率。最常見的選擇算子是基本遺傳算法中的比例選擇算子，即輪盤賭選擇，其基本思想是：個(gè)體被選中的概率與其適應(yīng)度大小成正比。但對(duì)于不同的問題，它并不都是最合適的選擇算子，所以又發(fā)展了其它選擇算子。最優(yōu)保留選擇是使當(dāng)前群體中適應(yīng)度最高的個(gè)體不參與交叉運(yùn)算和變異運(yùn)算，并用它來替換掉本代群體中經(jīng)過交叉、變異等遺傳操作后所產(chǎn)生的適應(yīng)度最低的個(gè)體；確定式采樣選擇的基本思想是按照一種確定的方式來進(jìn)行個(gè)體選擇；無放回隨機(jī)選擇又叫期望值選擇方法，它的基本思想是根據(jù)每個(gè)個(gè)體在下一代群體中的生存期望來進(jìn)行隨機(jī)選擇運(yùn)算；排序選擇的著眼點(diǎn)是個(gè)體適應(yīng)度之間的關(guān)系，它將群體中的所有個(gè)體按其適應(yīng)度大小進(jìn)行排序，基于這個(gè)排序來分配個(gè)體的被選中的概率；隨機(jī)聯(lián)賽選擇同樣基于個(gè)體適應(yīng)度的大小，基本思想是每次選取幾個(gè)個(gè)體，適應(yīng)度最高的一個(gè)個(gè)體將遺傳到下一代群體中。（2）交叉算子。交叉操作是遺傳算法具備的原始性的獨(dú)有特征。GA交叉算子是模仿自然界有性繁殖的基因重組過程，其作用在于將原有的優(yōu)良基因遺傳給下一代個(gè)體，并生成包含更復(fù)雜基因結(jié)構(gòu)的新個(gè)體。在交叉運(yùn)算之前，首先必須對(duì)群體中的個(gè)體進(jìn)行配對(duì)。常用的配對(duì)策略是隨機(jī)配對(duì)，即將群體中的N個(gè)個(gè)體以隨機(jī)的方式組成N/2對(duì)配對(duì)個(gè)體組，交叉運(yùn)算在個(gè)體組的兩個(gè)個(gè)體之間進(jìn)行。兩個(gè)相互配對(duì)的染色體按某種方式相互交換其部分基因，從而形成兩個(gè)新的個(gè)體。交叉算子的設(shè)計(jì)和實(shí)現(xiàn)與所要解決的問題密切相關(guān)，一般要求它既不要太多的破壞個(gè)體編碼串中表示優(yōu)良險(xiǎn)狀的模式，又能夠有效的產(chǎn)生出一些較好的新的個(gè)體模式。交叉算子的設(shè)計(jì)就是要確定交叉點(diǎn)的位置，然后進(jìn)行部分基因交換。最常見的交叉算子是單點(diǎn)交叉算子，它是指在個(gè)體編碼串中隨機(jī)設(shè)置一個(gè)交叉點(diǎn)，然后在該點(diǎn)互換兩個(gè)配對(duì)個(gè)體的基因。但單點(diǎn)交叉算子有一定的適用范圍。雙點(diǎn)或多點(diǎn)交叉是指在個(gè)體串編碼中隨機(jī)設(shè)置了兩個(gè)或多個(gè)交叉點(diǎn)，然后再進(jìn)行部分基因的互換；均勻交叉是指兩個(gè)配對(duì)個(gè)體的每一個(gè)基因座上都以相同的交叉概率進(jìn)行交換，從而形成兩個(gè)新的個(gè)體。（3）變異算子。在生物遺傳過程中，其細(xì)胞分裂復(fù)制環(huán)節(jié)有可能會(huì)因?yàn)槟承┡既灰蛩氐挠绊懚a(chǎn)生一些復(fù)制差錯(cuò)，導(dǎo)致某些基因的變異，從而產(chǎn)生新的染色體。模仿這個(gè)環(huán)節(jié)，在遺傳算法中也引入了變異算子來產(chǎn)生新的個(gè)體。變異是隨機(jī)改變某個(gè)個(gè)體遺傳信息的一種操作。遺傳算法中，交叉算子因其全局搜索能力而作為主要算子，變異算子因其局部搜索能力而作為輔助算子。遺傳算法通過交叉和變異這一對(duì)相互配合又相互競(jìng)爭(zhēng)的操作而使其具備兼顧全局和局部的均衡搜索能力，才能以良好的搜索性能完成最優(yōu)化問題的尋優(yōu)過程。在遺傳算法中使用變異算子主要的目的是：改善遺傳算法的局部搜索能力，維持群體的多樣性，防止出現(xiàn)早熟現(xiàn)象。變異的思想同交叉一樣，也是先確定變異點(diǎn)的位置，再進(jìn)行基因值的替換。最簡(jiǎn)單的變異算子是基本位變異算子，它是指對(duì)個(gè)體編碼串中以變異概率隨機(jī)指定的某一位或某幾位基因座上的基因值作變異運(yùn)算。為適應(yīng)不同的應(yīng)用問題的求解需要，還有其它的變異算子。均勻變異是指分別用符合某一范圍內(nèi)均勻分布的隨機(jī)數(shù)，以某一較小的概率來替換個(gè)體編碼串中各個(gè)基因座上的原有基因。非均勻變異是對(duì)原有基因值作以隨機(jī)擾動(dòng)，以擾動(dòng)后的結(jié)構(gòu)作為變異后的基因值。5.4.4編碼、初始群體生成及適應(yīng)度函數(shù)的設(shè)定（1）編碼:由于VRP問題用二進(jìn)制處理具有先天性的不足，為了彌補(bǔ)這一不足，本文采用自然數(shù)編碼，并用一個(gè)簡(jiǎn)單的例子加以分析。設(shè)0代表配送中心，自然數(shù)表示顧客點(diǎn)的編號(hào)，假設(shè)有5個(gè)顧客，隨機(jī)產(chǎn)生一個(gè)染色體01402350，表示調(diào)度方案為2臺(tái)車給5個(gè)顧客送貨，車輛11線路是“中心顧客1顧客4中心”，車輛21是“中心顧客2顧客3顧客5中心”。這種編碼方式能夠保證每輛車行駛線路的連通性。染色體長(zhǎng)度=車輛總數(shù)+顧客數(shù)+1。車輛總數(shù)需要事先試算，一般要求車輛總裝載容量是總貨物量的1.051.3倍，會(huì)產(chǎn)生幾種不同的車輛組合方案，然后針對(duì)不同方案進(jìn)行下一步優(yōu)化工作。（2）初始群體生成：任意給顧客和車輛排序；從左向右累計(jì)顧客需求量，若第一輛車容量大于前a個(gè)顧客需求量之和且小于前個(gè)a+1顧客需求量之和，則得第一輛車子串1“12a0”；刪去排序中前a個(gè)顧客，同理可得第二輛車子串2;如此反復(fù)，直到車輛和顧客被安排完;把子串順序連接,左端加0就得到一條初始染色體,重復(fù)操作,直到符合群體規(guī)模N。（3）適應(yīng)度函數(shù)：適應(yīng)度函數(shù)由目標(biāo)函數(shù)轉(zhuǎn)化得到，是染色體k的適應(yīng)度函數(shù)，是同代群體中最佳染色體的費(fèi)用，是染色體的費(fèi)用。適應(yīng)度最大的染色體對(duì)應(yīng)配送成本最低的調(diào)度方案。5.4.5群體更新過程群體更新過程就是更新當(dāng)前解群體，產(chǎn)生新一代解群體的過程：具體的講是從當(dāng)前解群體中選擇適應(yīng)度大的個(gè)體，進(jìn)行交叉、變異，生成新的解群體的過程，該過程是GA模擬自然進(jìn)化過程的重要體現(xiàn)，是促成算法逐步實(shí)現(xiàn)搜索到最優(yōu)解的根本原因。具體操作方法如下：（1）選擇算子。給N條染色體排序；計(jì)算適應(yīng)度；計(jì)算選擇概率；計(jì)算累積概率；產(chǎn)生0，1區(qū)間均勻分布隨機(jī)數(shù)R，若R，則選擇染色體1，否則選擇染色體K，使得重復(fù)進(jìn)行，直到符合群體規(guī)模n.為提高算法性能，保留上代群體中最佳染色體。 （2）交叉算子。按2個(gè)一串將雙親“01402350”和“02450130”基因分組，得0 14 02 350 和0 24 50 130 ；雙親中子串“14”兩端都為0，把“14”和所有“0”基因保留，填充到空白染色體相同位置上；刪去雙親2基因1和4，把剩余基因按順序填入空白位置，得后代1“01402350”。同理得后代2“02410350”。若所有子串兩端不全為0，則左移或右移“ ”，直到存在兩端為0子串。3點(diǎn)交叉算子操作原理類似。（3）變異算子。對(duì)2交換變異算子，在染色體中任意確定兩個(gè)非零基因，交換其位置，就得到1條新染色體。對(duì)交3換變異算子，任意確定3個(gè)非零基因，把它們位置按不同方式交換，可得到5條新染色體，選擇其中適應(yīng)度最大的染色體作為運(yùn)算結(jié)果。確定實(shí)際問題參數(shù)對(duì)參數(shù)編碼初始化群體確定評(píng)價(jià)群體滿足停止準(zhǔn)則（1）染色體編碼；（2） 計(jì)算目標(biāo)函數(shù)尋找最優(yōu)個(gè)體遺傳操作群體更新解碼得最優(yōu)解三個(gè)基本算子：（1） 選擇（2） 交叉（3） 變異No遺傳算法設(shè)計(jì)最后一步是確定控制參數(shù)和算法終止條件。推薦控制參數(shù)取值范圍是：群體規(guī)模n=20100，交叉率=0.40.99，變異率=0.0010.01，詳細(xì)根據(jù)具體情況確定，其流程圖如圖4-638所示。Yes圖 4-6 遺傳算法的基本流程Chart 4-6 heredity algorithm basic flow由以上步驟可以看出，可行解的編碼方法、遺傳算子的設(shè)計(jì)是構(gòu)造遺傳算法時(shí)需要考慮的兩個(gè)主要的問題，也是兩個(gè)關(guān)鍵的步驟，而對(duì)所求問題的理解是遺傳算法應(yīng)用成功的前提。5.5算例分析本論文的算例資料采用長(zhǎng)安大學(xué)龔延成等在數(shù)學(xué)的實(shí)踐與認(rèn)識(shí)2004年06月發(fā)表的，題目為：基于遺傳算法的物流配送車輛調(diào)度問題研究，是迄今為止我認(rèn)為比較全面的研究，他不僅綜合了以往的帶能力約束問題、帶時(shí)間窗限制的問題，還追加了多車種服務(wù)問題，可以說適用性更加廣泛，他的不足之處就是對(duì)顧客服務(wù)質(zhì)量沒有一個(gè)衡量的標(biāo)準(zhǔn)，只是通過懲罰成本來限制，在某些情況下，配送費(fèi)用雖然達(dá)到了最小化，但是顧客的滿意程度卻是較低的，這嚴(yán)重影響了以后的顧客服務(wù)源，給配送中心的長(zhǎng)遠(yuǎn)利益帶來了無形的損失。而本文則結(jié)合實(shí)際、考慮到顧客長(zhǎng)遠(yuǎn)的服務(wù)需求，在滿足上述約束條件的基礎(chǔ)上，將顧客滿意度作為約束條件引入模型當(dāng)中，使其更合理，因此本文采用這一算例，并且加入了模糊預(yù)約時(shí)間，即顧客在可以容忍的服務(wù)時(shí)間范圍中最滿意的時(shí)間段，通過計(jì)算將二者計(jì)算結(jié)果進(jìn)行比較分析，從而驗(yàn)證本文模型構(gòu)建的合理性。資料如下：某配送中心經(jīng)營(yíng)啤酒配送業(yè)務(wù)，每天向個(gè)客戶運(yùn)送箱裝的啤酒，有關(guān)數(shù)據(jù)如表1所示。測(cè)量比例為1：1000000，得到地圖中心坐標(biāo)為(60,140)，客戶坐標(biāo)，由于實(shí)際距離與空間測(cè)量距離有一定的差異性，根據(jù)經(jīng)驗(yàn)知：中心與客戶、客戶與客戶的最短運(yùn)距通過公式近似計(jì)算。平均速度間，送貨車輛有兩類，A類裝載容量是500箱，每公里車輛費(fèi)用3元，B類的裝載容量為400箱，每公里車輛費(fèi)用為2.5元。駕駛員正常工作每小時(shí)10元，加班補(bǔ)助每小時(shí)20元，途中運(yùn)行到12：00或18：00時(shí)安排30分鐘吃飯時(shí)間。車輛等待費(fèi)用每小時(shí)10元，客戶延遲費(fèi)用均為每小時(shí)100元。若最早發(fā)車時(shí)間為早晨6：30，試運(yùn)用本文所建模型確定路徑優(yōu)化方案。詳細(xì)的數(shù)據(jù)見表5.1客戶情況一覽表42。表5.1 客戶情況一覽表顧客啤酒箱數(shù)顧客位置（毫米）卸貨時(shí)間（分鐘）時(shí)間窗模糊預(yù)約時(shí)間X坐標(biāo)Y坐標(biāo)112030114608：0017：009：0011：3022004036908：0010：308：3010：3031204896608：0017：009：0015：00415052120808：0012：008：3011：30514092154708：008：308：008：306609266408：0017：0010：0015：00711094100608：0017：008：3011：308180108100908：0010：459：3010：3099044160508：008：308：008：30101602054908：0013：008：0012：001114010832608：0013：0010：3012：001215013088708：0017：009：0015：00合計(jì)1620820首先根據(jù)單車容量和1620箱的總運(yùn)量。車輛行駛路線可初步確定兩種派車方案。方案1：A型車2臺(tái)和B型車2臺(tái)，車輛總?cè)萘繛?800箱；方案2：A型車1臺(tái)和B型車3臺(tái)車輛總?cè)萘繛?700箱，染色體長(zhǎng)度12+4+1=17，采用2和3交叉算子，以及2和3交換變異算子，取群體規(guī)模n=20，交叉率=0.85，變異率=0.001，算法終止條件設(shè)定為：若迭代算法達(dá)到600代；若最佳染色體連續(xù)保持20代；若某代染色體的平均適應(yīng)度達(dá)到這一代最佳染色體適應(yīng)度的0.90倍。根據(jù)表5.1數(shù)據(jù)，通過計(jì)算得各點(diǎn)距離表如表5.4。表5.2各客戶點(diǎn)間的距離012345678910111200147.602127.194.40354.730.672.60425.927.4101.829.20541.988.5154.787.463.00696.894.472.063.980.6105.60763.078.6100.555.455.864.840.90875.095.1112.172.271.467.645.116.80930.757.7148.977.049.058.1126.793.7105.3010113.873.032.360.688.0147.787.6104.6119.2130.4011147.1135.881.7105.3125.2147.745.183.381.6171.7108.9012104.6124.0124.798.9101.291.452.745.530.1134.6138.272.20運(yùn)算結(jié)果如下：方案1總費(fèi)用是2909.73元，詳細(xì)結(jié)果參見表5.3和表5.4，車輛行駛路線如圖5-5 所示。9541381227610211物流中心 160 140 120 100 80 60 40 20 40 60 80 100 120 140圖 5-5 車輛行駛路徑示意圖Chart 5-5 vehicles travel way schematic drawing雖然方案2車輛平均實(shí)載率大于方案1，但其總費(fèi)用卻大于方案1，這是由于方案2的車輛容量約束太緊，導(dǎo)致總行駛里程顯著增大，各項(xiàng)費(fèi)用增加，因此，采用車輛調(diào)度方案1是經(jīng)濟(jì)合理的。表5.3車輛調(diào)度計(jì)算結(jié)果序號(hào)車型車輛容量/最大總里程路程總時(shí)間車輛費(fèi)用駕駛費(fèi)用總費(fèi)用裝載量（箱）（公里）（小時(shí)）（元）（元）（元）1A500/4802759.1824.0491.56915.602B400/3201854.6461.1845.75506.933A 500/46032310.2967.72114.201081.924B400/3601426.0354.1055.28409.39合計(jì)1800/162092529.92607.04306.792913.83表5.4車輛調(diào)度計(jì)算結(jié)果線路車輛路徑路徑里程（公里）和車輛裝載量（箱）變化情況1021030127323211448028012002058042687503201800307121160634672455304603502006004091403158272604602701500通過表格可以看出運(yùn)用本文算法得出的方案：A類車輛11行駛路徑為021030，車輛12行駛路徑為07121160；B類車輛21行駛路徑為0580，車輛22行駛路徑為09140。通過比較，可以看出本文計(jì)算結(jié)果與參考資料結(jié)果有如下不同：（1）參考資料車輛11行駛路徑為032100，而本文計(jì)算結(jié)果為021030，參考資料行駛路徑長(zhǎng)度為274千米，而本文計(jì)算的行駛路徑長(zhǎng)度為275千米，相差1千米；（2）根據(jù)參考資料所給出的計(jì)算過程計(jì)算應(yīng)得總費(fèi)用為2913.83元，而本文計(jì)算結(jié)果為2918.83元，本文計(jì)算的總費(fèi)用雖然比參考資料計(jì)算的多2913.83-2909.73=4.1元，但是本文有一個(gè)較原計(jì)算優(yōu)異的方面，就是本文是在充分考慮顧客滿意度的基礎(chǔ)上得到的結(jié)果，從長(zhǎng)遠(yuǎn)的角度考慮，它可以提高配送中心的服務(wù)質(zhì)量，取得長(zhǎng)遠(yuǎn)效益，而且減少了無形的損失，即由于顧客不滿意企業(yè)服務(wù)質(zhì)量而選擇其他企業(yè)服務(wù)的損失，相信只需付出4.1元就能達(dá)到拴住顧客實(shí)現(xiàn)長(zhǎng)期服務(wù)是值得的。（3）根據(jù)顧客滿意度隸屬函數(shù)計(jì)算可以知道通過本文的優(yōu)化方案顧客平均滿意度達(dá)到91.67%，遠(yuǎn)遠(yuǎn)大于約束條件當(dāng)中要求的80%，而按照參考資料的行駛路徑032100,根據(jù)本文對(duì)顧客滿意度的定義，它的顧客平均滿意度是75.28%，相比之下，本文所構(gòu)建的模型考慮的相對(duì)全面周到一些。通過比較分析，可以看出本文在構(gòu)建模型時(shí)充分考慮了動(dòng)態(tài)的因素，不再單單以短期效益為目的，以路徑最短、費(fèi)用最小等直觀的因素為目標(biāo)、為條件，而是更多地考慮到配送中心的長(zhǎng)期效益，將影響配送中心效益的顧客滿意度給以相應(yīng)的期望值，在此基礎(chǔ)之上進(jìn)行計(jì)算，使之更合理。5.6本章小結(jié)本章從功能設(shè)計(jì)的角度，對(duì)GPS在應(yīng)用中涉及的功能進(jìn)行詳細(xì)描述并進(jìn)行了總體框架設(shè)計(jì)；GIS的設(shè)計(jì)主要從客戶定位、道路狀況等要素，進(jìn)行了電子地圖基礎(chǔ)工作的實(shí)現(xiàn)，對(duì)可視化效果進(jìn)行展示。在模型的計(jì)算過程中，由于采用的是遺傳算法這一優(yōu)化方法的邏輯思維，將其應(yīng)用到MATLAB編程當(dāng)中。通過具體的算例，應(yīng)用MATLAB程序計(jì)算，將計(jì)算結(jié)果與原參考算例的計(jì)算結(jié)果進(jìn)行比較，驗(yàn)證模型的合理性。結(jié) 論本文結(jié)合北大倉(cāng)啤酒有限公司的實(shí)際，使用了GPS、GIS、配送系統(tǒng)，通過對(duì)路徑優(yōu)化問題中顧客滿意程度進(jìn)行集中研究，建立現(xiàn)代物流配送路徑優(yōu)化問題的模型。物流配送環(huán)節(jié)的整體優(yōu)化，提高了管理水平與效率，降低了成本，達(dá)到了物流配送優(yōu)化的目標(biāo)，為實(shí)現(xiàn)現(xiàn)代物流做出了有益探索。本文的創(chuàng)新點(diǎn)就是通過模糊評(píng)價(jià)建立顧客滿意度函數(shù)，并將其作為首要約束條件對(duì)路徑優(yōu)化選擇進(jìn)行制約，將遺傳算法和MATLA