陳小麗， 曲 媛， 肖 鴻

(1．同濟大學鐵道與城市軌道交通研究院，上海201804;2．上海市城市建設設計研究總院，上海200125;3．北京交通大學交通運輸學院，北京100044)

0 引言

配送是物流活動中直接與消費者相連的重要的環(huán)節(jié)，在物流的各項成本中，配送成本占了相當高的比例[1]．因此，配送線路是否合理直接影響著配送的速度、成本和效益等，如何科學合理地確定配送活動中的配送線路是一項非常重要的工作．

目前煙草行業(yè)的很多商業(yè)企業(yè)已經(jīng)實行由物流中心直接配送到戶的對接配送模式．本文針對宜春市煙草公司各分公司的需求情況、道路交通網(wǎng)、企業(yè)車輛及運行限制等因素進行了較充分的分析，利用節(jié)約里程算法對公司的配送區(qū)域和線路規(guī)劃進行設計與優(yōu)化．結果較為理想，可降低運輸成本，提高效益．

1 節(jié)約算法

節(jié)約算法是用來解決運輸車輛數(shù)目不確定的VRP問題，它是迄今為止用來解決VRP模型最常用的一種啟發(fā)式算法．

節(jié)約算法主要步驟

基本條件:已知車輛的集合NT={1，2，…，m}，各車輛最大載重量為Wi，各配送節(jié)點組成的點集為NR={1，2，…，n}，各節(jié)點的需求量為Ri，各個節(jié)點之間的最短距離為cij．

(1)將車輛按照最大載重量從大到小依次排序，滿足W1≥W2≥ … ≥Wi≥ … ≥Wn．

(2)計算所有的客戶對(i，j)的節(jié)約里程的Δcij值，其中

將其中大于0的Δcij從大到小依次排成隊列．

(3)求可行解．確定各車輛的配送點集I1，I2，…，Im，令Ij={j}，(j=1，2，…，n)(先對各點進行單點配送)．

(4)合并配送路徑．直到節(jié)約里程Δcij的隊列空為止，重復下列步驟:按照節(jié)約里程Δcij隊列從大到小的順序，分析客戶i和j之間合并的可能性(是否滿足裝載限制條件、不在同一路徑內以及合并次數(shù)不超過2)，將i，j連接起來，即可令Ii'=Ii∪Ij;Ij=?．如果不是這樣，則從節(jié)約里程隊列中去除當前的節(jié)約里程，分析下一個客戶對[2]．

2 VRP模型的建立

2．1 VRP 模型

多回路運輸問題現(xiàn)實生活中十分普遍的一種調配問題．解決此類調配問題時，核心問題是如何對車輛進行調度．因此就出現(xiàn)了VRP模型，并成為解決這種運輸問題的一個很成功的模型．

VRP模型問題描述為:確定一個配送中心，該中心有N輛車，對M個節(jié)點進行配送，每個節(jié)點的需求量是Ri(i=1，2，…，n)，每輛運輸車輛的載重限制是D．設cij表示節(jié)點i到節(jié)點j的運輸成本，如時間、路程和花費等．[3]配送中心編號為0，各配送節(jié)點標號為i(i=1，2，…，n)，定義變量如下:

建立此問題的數(shù)學模型:

該模型中，式(3)為車輛的容量約束;式(4)保證了每個節(jié)點的運輸任務僅由一輛車完成，而所有運輸任務則由N輛車協(xié)同完成;式(5)和式(6)限制了到達和離開某一節(jié)點的車輛有且僅有一輛[3]．

圖1 原有配送線路圖

圖2 節(jié)約算法求解線路結果

2．2 以宜春市煙草公司為例建模

2．2．1 宜春市煙草公司配送現(xiàn)狀分析

宜春市煙草公司位于宜春市袁山大道，旗下設有十個分公司．該公司總部設有一個總配送中心，由該中心向旗下的十個分公司進行配送，再由十個分公司的配送中心將卷煙送往各地的零售商．由于需求量不斷增大，現(xiàn)今該公司實行每日定點定量配送．需求量大的縣市日需求量達到460多件，需求量小的縣市則為60多件．公司現(xiàn)擁有5輛5t的貨車，5 輛2．5t的貨車，5t貨車可裝卷煙 330 件，2．5t貨車可裝卷煙150件，每件卷煙約15kg，所以當貨車裝滿時仍然不會超重．

現(xiàn)在公司采用的是“點到點”的直接配送模式．其配送模式如圖1所示．共需10輛貨車，該模式的缺陷在于:首先，配送線路選擇不夠合理，沒有得到優(yōu)化，導致配送成本過大;其次，采用此種模式使得剩余貨運量在進行直接配送時出現(xiàn)貨車裝不滿，造成資源浪費，導致配送成本進一步加大，嚴重影響公司的效益．

2．2．2 模型的目標

確定所需要的車輛的總數(shù)n、車輛的類型以及它們的路線，并將這些車輛放在同一個回路中，同時包括回路內的路線安排和調度，使總費用最?。?．2．3 限制條件

(1)基于人性化的考慮，司機每天工作不超過6小時(配送車輛的車速一般控制在50km/h．)由于在本模型中考慮時間窗的限制會加大解題的難度，因此對配送時間的限制轉換為在規(guī)定時間內對行駛里程的限制，即各車最大運輸距離為500km．

(2)完成任務之后每輛車都要回到0處．

(3)不允許超過車輛的最大容量限制．由于用一輛5t貨車的運量約為2．5t貨車的2倍，并且在運輸路徑、物流成本方面也會有很大的節(jié)約，因此先選用5t的貨車限制容量．5t貨車最多裝330件，2．5t貨車最多裝150件．

3 運用節(jié)約算法對宜春市煙草公司物流配送線路進行優(yōu)化

已知市煙草公司為0點，分別向10個分公司配送卷煙，其擁有5輛5t的貨車和5輛2．5t的貨車，5t貨車最大載重量為330件，2．5t貨車最大載重量為150件，設各點間的距離為C，C={cij|i，j=1，…，10}，節(jié)約距離為 Δcij．每輛車的載重量為ri，各點需求量為Ri(i=1，…，10)，每輛車的行駛里程為Li(i=1，…，10)，且Li≤500km，袁州區(qū)為0 點，客戶點1，2，…，10，現(xiàn)有的配送量如表1．

車輛調度采用以下方案:按需求量的多少選配車輛．如，袁州區(qū)分公司的需求量為372件，可先采用1輛5t貨車進行一次直接配送，剩余42件使用節(jié)約算法的原理進行配送，其他各縣市的貨運量均按該方法進行整理，整理后如表2所示．

3．1 運用節(jié)約算法優(yōu)化配送線路

在表2中，采用節(jié)約算法對有剩余貨運量的10個縣市進行配送線路優(yōu)化．

3．1．1 確定各配送點間的最短距離

因為cij=cji，各分公司間最短距離如表3所示．

表1 現(xiàn)有配送任務表

表2 整理后的配送任務表

表3 各分公司間最短距離表(單位:km)

表4 節(jié)約里程順序表 (單位:km)

3．1．2 求節(jié)約里程

根據(jù)最短距離表，計算出用戶間的節(jié)約里程，并由大到小排列，編制節(jié)約里程Δcij順序表，如表4所示．

3．1．3 求初始解

令Ii={i}(i=1，…，10)，最短路徑Li=2c0i(i=1，…，10)，且Li≤500km，載重量ri=Ri，且Ri≤330件，對10個客戶點進行標記B1=B2=…=B10=0，且Bi≤2．

3．1．4 優(yōu)化結果

按節(jié)約里程從大到小合并路徑得到的優(yōu)化結果如表5所示，優(yōu)化線路結果如圖2所示．

表5 節(jié)約算法優(yōu)化結果

總運輸里程為所有路徑之和，求得為1390．2km，共需5t車4輛．與優(yōu)化前相比，節(jié)約了5輛2．5t的車，節(jié)約里程數(shù)為1018．2，使得公司的配送效率大大提高．

[1] 雷同飛，張宏．物流配送中的車輛路徑優(yōu)化問題[J]．商場現(xiàn)代化，2009(1):119 －120．

[2] 劉利軍．張裕集團葡萄酒配送線路優(yōu)化研究[J]．山東工商學院學報，2006(1):98．

[3] 蔡臨寧．物流系統(tǒng)規(guī)劃—建模實例分析[M]．北京:機械工業(yè)出版社，2003．