基于容量約束的城市共同配送路線優(yōu)化

馬秀麗

（湖州職業(yè)技術(shù)學(xué)院，浙江 湖州 313000）

基于容量約束的城市共同配送路線優(yōu)化

馬秀麗

（湖州職業(yè)技術(shù)學(xué)院，浙江 湖州 313000）

在城市共同配送中，對(duì)配送路線進(jìn)行優(yōu)化十分重要。介紹了CVRP模型以及城市共同配送的路線優(yōu)化方法，著重分析了節(jié)約里程法的原理和計(jì)算步驟，最后通過實(shí)例，描述了不同優(yōu)化方法的應(yīng)用，并選出了最優(yōu)的方法。

CVRP模型；城市共同配送；路線優(yōu)化

1 引言

2015年8月，湖州正式成為了浙江省開展城市共同配送的兩個(gè)試點(diǎn)城市之一。湖州市商務(wù)局在公平、公開、公正的基礎(chǔ)上，精心挑選了6家企業(yè)分別從事不同商品的城市配送，配送的商品涉及城市快速消費(fèi)品、家電、醫(yī)藥、酒、食品、生鮮、書報(bào)等。經(jīng)過一年半的建設(shè)，湖州城市共同配送標(biāo)準(zhǔn)化建設(shè)初具規(guī)模，城市配送車輛按照《城市物流配送汽車選型技術(shù)要求》（GB/T29912）進(jìn)行選擇。隨著“互聯(lián)網(wǎng)+高效物流”工作的推進(jìn)，客戶對(duì)配送質(zhì)量的要求越來越高，要在遵循湖州城市交通政策前提下，有效地將客戶需要的貨物送至目的地，各公司就必須開展不同形式的共同配送。在大數(shù)據(jù)、云計(jì)算、移動(dòng)互聯(lián)等技術(shù)日趨成熟的今天，在考慮車輛容積、了解客戶分布的基礎(chǔ)上，計(jì)算最佳配送路線是本文所要研究的問題。

2 CVRP模型

CVRP即有能力約束的車輛路徑調(diào)度（Capacitated Vehicle Routing Problem，CVRP），簡稱“車輛路徑問題”。該模型約束少，一般僅對(duì)車輛的載重和行駛的時(shí)間（或距離）有約束。

CVRP基本原理是：若干有配送需求的客戶被一組配送車輛服務(wù)，這些配送車輛從物流中心出發(fā)，沿途為不同的客戶送貨。每輛配送車輛具有相同裝載容量上限，每位客戶具有特定的配送量需求,每位客戶只能被一輛車服務(wù)，所有的配送車輛從物流中心出發(fā),送完貨,再回到物流中心，一輛車不能在同一個(gè)客戶處停留多次，所有的配送車輛都不能超載，一條線路上所有客戶的配送量之和不能超過該輛車的額定載重量。用所有配送車輛行駛的距離總和來衡量一個(gè)解的質(zhì)量，且要求配送總成本最低。

CVRP的描述：設(shè)某物流中心自有k輛車，每輛配送車的最大載重量為Q，需要對(duì)n個(gè)客戶(節(jié)點(diǎn))進(jìn)行運(yùn)輸配送，每輛車從物流中心出發(fā)給若干個(gè)客戶送貨，最終回到物流中心，客戶點(diǎn)i的貨物需求量是qi(i=1,2,…,n)，且qi〈Q。記物流中心編號(hào)為0，各客戶編號(hào)為i(i=1,2,…,n)，cij表示客戶i到客戶j的距離。求滿足車輛數(shù)最小、車輛行駛總路程最短的配送方案。

定義變量如下：

建立此問題的數(shù)學(xué)模型：

約束條件：

3 城市共同配送的線路優(yōu)化方法

一般來說，城市共同配送的配送線路是指一輛配送車輛離開物流中心，按照一定順序訪問若干客戶點(diǎn)后返回起點(diǎn)的行駛路線。在湖州市開展城市共同配送的過程中，各實(shí)施共同配送的物流中心以降低成本、減少污染、提高配送效率為配送路線的優(yōu)化原則。因?yàn)槌杀九c路程相關(guān)性較強(qiáng)，而和其他因素的相關(guān)性較小，所以選擇最短路徑作為目標(biāo)。以路徑最短作為配送路線優(yōu)化目標(biāo)有兩種方式：

3.1 直送式配送線路優(yōu)化

直送式配送又稱一對(duì)一的配送，即一個(gè)物流據(jù)點(diǎn)對(duì)應(yīng)一個(gè)客戶的專線送貨。在直送式配送方法下，需要一定的約束條件，也就是一個(gè)客戶的需求量接近或大于可用車輛的額定重量，專門派一輛或多輛車進(jìn)行一次或多次送貨。這種配送方式體現(xiàn)的是多裝快跑，選擇最短配送線路，以節(jié)約時(shí)間、費(fèi)用，提高配送效率，進(jìn)行一對(duì)一配送，在物流配送線路圖中尋找最短路徑是最合適的方法，可以利用百度地圖等電子地圖直接找到最短路徑，理論上可以用位勢(shì)圖、破圈法等技術(shù)。

3.2 分送式配送運(yùn)輸線路優(yōu)化

分送式配送又稱一對(duì)多的配送，即由一個(gè)物流中心對(duì)多個(gè)客戶實(shí)行共同送貨。這種配送方式的約束條件是同一條線路上所有客戶的需求量總和不超過一輛車的額定載重量，送貨時(shí)，由這一輛車裝著所有客戶的貨物，沿著事先規(guī)劃好的最優(yōu)路線一一將貨物送到各個(gè)客戶手中，這樣既保證按時(shí)按量將用戶需要的貨物及時(shí)送到，減少了使用車輛數(shù)量，節(jié)省了費(fèi)用，也緩解了交通緊張的壓力，減少了運(yùn)輸對(duì)環(huán)境造成的污染。利用節(jié)約里程法確定配送路線的主要出發(fā)點(diǎn)是，根據(jù)配送方的運(yùn)輸能力及其到客戶之間的距離和各客戶之間的相對(duì)距離來制定使配送車輛總的周轉(zhuǎn)量達(dá)到或接近最小的配送方案，一般采用節(jié)約里程法路線設(shè)計(jì)技術(shù)。

在湖州城市共同配送過程中，通過考察6家物流公司的配送情況，發(fā)現(xiàn)一個(gè)客戶的配送需求幾乎沒有達(dá)到車輛額定載重量的情況，并且客戶分布不太集中，因此將多個(gè)客戶集中起來進(jìn)行整合、分揀、配貨，實(shí)行共同配送，以降低送貨成本。一般來說，客戶的配送需求以及貨品類型都是多樣化的，物流中心應(yīng)該按照貨品類型、配送目的地對(duì)貨品進(jìn)行分配配送，以優(yōu)化資源配置，降低運(yùn)輸成本。

4 節(jié)約里程法

4.1 節(jié)約里程法基本原理

圖1 節(jié)約里程法原理圖

如圖1所示，三角定理：a+b＞c；分別配送：2a+2b；巡回配送：a+b+c；所以(2a+2b)-（a+b+c）=a+b-c＞0，由此得出，走巡回配送路線比走分別配送路線更節(jié)約里程。

4.2 節(jié)約里程法假設(shè)條件配送的是同一種或相類似的貨物；各用戶的位置及需求量已知；配送方有足夠的運(yùn)輸能力；節(jié)約里程法路線要求使總的周轉(zhuǎn)量最小外，還應(yīng)滿足所有客戶的到貨時(shí)間要求；不使車輛超載；每輛車每天的總運(yùn)行時(shí)間及里程滿足規(guī)定的要求。

4.3 節(jié)約里程法的計(jì)算步驟

利用節(jié)約里程法實(shí)現(xiàn)一個(gè)物流中心同時(shí)對(duì)多個(gè)客戶的配送，使得配送成本最低，具體計(jì)算步驟如下：

（1）通過百度地圖等電子地圖找出物流中心至客戶以及各客戶相互間的最短線路（距離），畫出最短距離矩陣。

（2）從最短距離矩陣中，計(jì)算客戶相互間的節(jié)約里程，即計(jì)算a+b-c的值。

（3）將節(jié)約里程按大小順序進(jìn)行降序排序。

（4）在滿足車輛額定裝載量、客戶需求量、送貨時(shí)間限制以及客戶地理位置等的條件下，按照節(jié)約里程從大到小連線，組成回路配送線路。從節(jié)約里程排序表找出產(chǎn)生該節(jié)約里程的兩個(gè)配送點(diǎn)i、j，再判斷連接i、j的回路是否存在合并的可能性。如果一個(gè)回路以（p，i）開始，一個(gè)回路以（j，p）結(jié)束，且滿足需求量和車載量等約束條件，則該回路可以合并，并進(jìn)行下面的合并操作：刪除兩個(gè)回路中的部分路徑（i，p）和（p，j），然后引入新的連接（i，j），得到新的回路（p，…，i，j，…，p）。重復(fù)上述過程，直至沒有可以合并的回路，從而得出配送優(yōu)化方案。

5 節(jié)約里程法在城市共同配送中的應(yīng)用

5.1 基礎(chǔ)信息

湖州祥瑞物流中心是湖州市城市共同配送中配送貨物量最大、運(yùn)作最為規(guī)范的物流公司。該公司涉足家電、醫(yī)藥、酒、食品等商品的城鄉(xiāng)配送業(yè)務(wù)，發(fā)展至今逐步建成了較為成熟的配送網(wǎng)絡(luò)，覆蓋了全市150多個(gè)鄉(xiāng)鎮(zhèn)，計(jì)劃在“十三五”期間實(shí)現(xiàn)全市鄉(xiāng)鎮(zhèn)配送全覆蓋。該公司在標(biāo)準(zhǔn)化建設(shè)方面領(lǐng)先其他5家中標(biāo)的公司，經(jīng)過一年多的建設(shè)，倉儲(chǔ)和配送標(biāo)準(zhǔn)化建設(shè)基本完成。購置了50輛不同規(guī)格的標(biāo)準(zhǔn)化市內(nèi)配送車輛，具體車輛信息見表1。

某日，湖州祥瑞物流中心配送部接倉儲(chǔ)部通知，需要為7家客戶配送商品，商品情況見表2，百度地圖中各客戶相對(duì)位置如圖2所示。

表1 市內(nèi)配送車輛信息及成本表

根據(jù)市場(chǎng)油價(jià)情況，汽油費(fèi)用為6.66元/升。

表2 各客戶需配送商品量

圖2 各客戶具體位置

客戶3

5.2 配送路線優(yōu)化

（1）最短距離矩陣表。通過百度電子地圖，找出物流中心至客戶以及客戶之間的最短距離，見表3。其中P0表示祥瑞物流中心，P1為客戶1，P2為客戶2，以此類推。

表3 物流中心至客戶以及客戶之間的最短距離表

（2）節(jié)約里程表。根據(jù)表3計(jì)算各客戶的節(jié)約里程，即計(jì)算a+b-c的值，得出表4。

表4 各客戶的節(jié)約里程表

（3）節(jié)約里程表排序。根據(jù)節(jié)約里程表，把節(jié)約里程由大到小排序，得到表5。

表5 節(jié)約里程排序表

（4）配送路線優(yōu)化方案。

①采用直送式（物流中心對(duì)客戶實(shí)行一對(duì)一送貨）。因?yàn)樾枰拓浀目蛻粲?家，每家配送量均沒有超過祥瑞物流中心最小車輛的貨物額定載重量（即國家標(biāo)準(zhǔn)中定義的載重量）500kg。所以采用直送式需要7輛車型Ⅰ的車，配送方案見表6。

表6 直送式配送方案

②節(jié)約里程法優(yōu)化配送方案。根據(jù)公式（6）和表2，利用節(jié)約里程法得到最優(yōu)路線方案見表7。

對(duì)比表6與表7，節(jié)約里程法比直送式節(jié)約里程：407km－180.9km＝226.1km，配送成本節(jié)約：395.27元－187.73元＝207.54元。優(yōu)化后的配送路線圖如圖3所示。

圖3 配送路線優(yōu)化方案

6 結(jié)束語

鑒于城市共同配送貨物的性質(zhì)，大部分屬于按重量計(jì)量的貨物，采用本文的方法，確實(shí)可以為物流中心節(jié)約大量成本。隨著城市共同配送中“互聯(lián)網(wǎng)+高效物流”的推進(jìn)，OTO訂單日趨增多，客戶也越來越分散，這就需要物流中心利用電子地圖將城市劃分為不同的配送區(qū)域，結(jié)合配送區(qū)域內(nèi)總配送量，再考慮車輛載重量，采用節(jié)約里程算法進(jìn)行配送。

[1]姜櫻梅,王淑云.乳品逆向物流及其VRP模型應(yīng)用[J].企業(yè)經(jīng)濟(jì),2014,(2)：60-63.

[2]陳磊,霍永亮,霍波陶.基于混合遺傳算法的物流車輛調(diào)度優(yōu)化[J].重慶師范大學(xué)學(xué)報(bào)(自然科學(xué)版),2015,32(2)：7-12.

[3]鄺海山.網(wǎng)購環(huán)境下城市共同配送動(dòng)態(tài)車輛調(diào)度優(yōu)化研究[D].重慶：重慶大學(xué),2014.

[4]王君,李波,盧志剛.帶時(shí)間窗動(dòng)態(tài)車輛路徑問題的優(yōu)化調(diào)度策略[J].計(jì)算機(jī)工程,2012,38(13).

Optimization of Urban Joint Distribution Route Based on Capacity Constraint

Ma Xiuli
(Huzhou Vocational&Technical College,Huzhou 313000,China)

In this paper,we introduced the CVRP model and the route optimization method for urban joint distribution,then focused on the principle and calculation steps of the saving algorithm,and at the end,through a practical example,described the application of different optimization processes.

CVRP model;urban joint distribution;route optimization

F224.0；F252.14

A

1005-152X(2017)06-0137-04

10.3969/j.issn.1005-152X.2017.06.032

2017-05-09

馬秀麗（1973-），女，山東汶上人，湖州職業(yè)技術(shù)學(xué)院講師，湖州現(xiàn)代物流研究所研究員，碩士，研究方向：物流與供應(yīng)鏈管理。