【文章內(nèi)容簡介】 本在公司總成本中所占比例日益增大。距離是影響運輸成本的主要因素，因為它直接對勞動、燃料和維修保養(yǎng)等變動成本發(fā)生作用。針對公司當前成本構(gòu)成狀況，可以知道：通過優(yōu)化公司配送路線，減少運輸車輛行駛總里程，可以減少車輛燃油費和道路服務(wù)費支出，進而減少物流總成本。因此，本文針對家樂福配送中心車輛路線優(yōu)化問題，提出的目標是：總運輸成本最小化。594配送中心632781配送中心分店車輛路線圖31 家樂福的配送模式此問題可以描述為：這是一種分送式配送模型,是由一個供應(yīng)點對多個客戶的共同配送。對配送中心負責的需求網(wǎng)點（家樂福分店），確定適當?shù)呐渌蛙囕v行駛路線，使其從配送中心出發(fā)，有序地通過各個分店各一次，最后返回配送中心，并在滿足一定的約束條件下(如車輛容量限制、行駛里程限制、時間限制、顧客需求量、交發(fā)貨時間等)，達到費用最少的目標。本文研究的是不考慮時間窗的非滿載車輛優(yōu)化調(diào)度問題。表述如下：將貨物從配送中心配送到各分配送中心,由分配送中心派出容量為的貨車承運，現(xiàn)有m輛車，各分店對所需求的貨物有一定的要求，第i個分店的貨運量為gi，（i=1，2……l）已知，在途中只有卸貨任務(wù),完成任務(wù)后返回配送中心,求滿足配送需求的費用最少行車線路。分配送中心1分配送中心2分配送中心3..........................分店1分店2分店3分店4.............配送中心圖32家樂福配送體系結(jié)構(gòu) 模型的構(gòu)建為建模方便，需考慮以下幾個前提假設(shè)條件：（1）配送中心不會出現(xiàn)缺貨的可能并且對顧客的基本配送資料（需求量、地理位置）為已知，配送中心的位置也已知；（2）不考慮配送時間限制，即客戶對貨物的需求沒有時間窗的規(guī)定；（3）不考慮每輛車為每個客戶的服務(wù)時間，即不考慮每個客戶的卸貨時間；（4）一個配送中心根據(jù)配送條件可以負責多個客戶，即一個配送中心服務(wù)多個客戶；（5）車輛由配送中心出發(fā)，服務(wù)被指定的需求點后，再返回配送中心，區(qū)域內(nèi)的需求點假設(shè)為固定數(shù)量且位置已知，不發(fā)生變動。（6）配送中心擁有一定數(shù)量的單一車型的配送車輛，且每輛車的容量已知。（7）每條配送路徑上各客戶需求量之和不超過配送車輛的容量；（8）每個客戶只能由一輛配送車輛送貨；（9）每輛車配送總里程不超過其最大行駛距離；（10）各道路均順暢，不考慮交通堵塞擁擠等特殊情況。將配送中心編號為0，車輛編號為k，任務(wù)編號為i=1,2........, 所有車型載重量單一，每輛汽車的最大載重量為g，需要向L個需求點送貨，每個需求點的需求量為，并且滿足，需求點i到j(luò)的運距為，配送中心到各個需求點的距離為，再設(shè)為第輛汽車配送的需求點數(shù)（=0表示未使用第輛汽車），用集合表示第k條路徑，其中的元素表示需求點在路徑中的順序為（不包括配送中心），令=0表示配送中心，為每輛車單位里程的行駛費用，為每輛車的派遣費用，考慮運輸量約束,停車點車輛數(shù)目等約束,可以定義如下的基本模型: (31) (32) (33) (34) (35) (36) 在上述模型中各個公式所代表的涵義如下：（31）式為目標函數(shù)，求總的配送費用最低；（32）式用于保證每條路徑上各個需求點的需求量和不超過汽車的載重量；（33）式表明每條路徑上的需求點數(shù)不超過總需求點數(shù)；（34）式表明每個需求點都得到配送服務(wù)；（35）式表示每條路徑的需求點的組成；（36）式表示當?shù)谳v汽車服務(wù)的客戶數(shù)大于或等于1時，說明該輛汽車參加了配送，則取，當?shù)趉輛汽車服務(wù)的客戶數(shù)小于1時，表示未使用該輛汽車，因此取； 節(jié)約算法節(jié)約算法的核心思想是將運輸問題中存在的兩個回路（0，… ，i，0）和（0，j，… ，0）合并成一個回路（0，… ，i，j，…，0）。在上面的合并操作中，整個運輸問題的總運輸距離會發(fā)生變化，如果變化后總運輸距離下降，則稱節(jié)約了運輸距離[6]。相應(yīng)的變化值，叫做節(jié)約距離，如式（1）所示。 （1）調(diào)整過程如圖3所示。jji 00i 調(diào)整前 調(diào)整后 圖33節(jié)約算法的圖像描述已知條件:需求點集={1,2,…, n},各點需求量,各點間最短距離。第一步,形成一個初始解。確定各車輛配送點集令, =1,2,…,n (先采取單點配送)。第二步,進行節(jié)約度的計算。計算所有點對的節(jié)約度△Cij，然后對計算結(jié)果進行升序排列。第三步，進行回路的合并。從升序排列的節(jié)約度序列中的最上面的值開始，直到節(jié)約里程△Cij的隊列空為止,重復(fù)下列步驟:按照節(jié)約里程△Cij隊列從大到小的順序,分析客戶i和j之間合并的可能性(是否滿足裝載限制條件、不在同一路徑內(nèi)以及合并次數(shù)不超過2),將i, j連接起來,即可令。如果不是這樣,則從節(jié)約里程隊列中去除當前的節(jié)約里程，分析下一個客戶對。表32 每個分店（一年365天）平均每天的需求量分店12345678910需求量（噸）2324123513分店11121314151617181920需求量（噸）2342121322現(xiàn)有路線是固定不變且為已知,每條線路行駛距離可由表32求得, 配送中心與商店之間，商店與商店之間的距離分析如下表：表33 配送中心與分店之間,分店與分店之間的距離(0點表示配送中心)0123456789101112131415161718192000122230171716131511511151120131139621727152313625621302136101611191614181310132112301834513131411201515194221121180501431128103826153317181436175303936345003745264143402025362434413915336105143701824121201123717616134502632202712143112821111331261826027252311182141617121791771914124127032182813201328101616118432503118261115281113141040230291652414261215271820382024323231290142420232423131513262512201118181614011111714101410153611852411019125221511231315332420272282624111901618191119165117341214131120160101917111318411114162015142317121810026151865143917132414519024191525211936152331122828261022111926240192061217331217231915190設(shè)每個車輛的運輸能力是8噸，根據(jù)案例可知，家樂福平均每天所用車輛數(shù)為12輛。現(xiàn)在用節(jié)約算法對該配送線路問題進行求解。根據(jù)配送中心與分店之間,分店與分店之間的距離距離表，計算出用戶間的節(jié)約里程， 表34 節(jié)約值矩陣表12345678910111213141516171819201020304230532060723208092227617010303011253180120125000101301416015002010100161011010910000170150148121034601801921301432151002060，其對應(yīng)的兩點為7。7兩處的需求量之和為7，未超過一輛車的運輸能力8，因此，連接7成回路。表3512345678910111213141516171819201020304230532060