1.2 配送車輛優化調度問題概述

1.2.1 配送車輛優化調度問題的描述

配送車輛優化調度問題可以描述為：在一個存在供求關系的系統中，有若干臺車輛、若干個配送中心和客戶，要求合理安排車輛的行車路線和出行時間，從而在給定的約束條件下，把客戶需求的貨物從配送中心送到客戶，把客戶供應的貨物從客戶取到配送中心，并使目標函數取得優化。

配送車輛優化調度問題可歸結為如下的一般網絡模型：設G=（V，E，A）是一個連通的混合網絡，V 是頂點集（表示配送中心、客戶、停車場等），E、A 分別為無向的邊集和有向的弧集，E中的邊和A中的弧均被賦權（可以表示配送的距離、時間或費用），V′、E′、A′分別為V、E、A的子集，求滿足約束條件（包括客戶的貨物需求或供應數量約束、需求或供應時間約束、配送車輛一次配送的最大行駛距離約束、車輛的最大載重量約束等），并包含V′、E′、A′的一些巡回路線，使目標函數取得優化，目標函數可以取配送總里程最短、配送車輛總噸位公里數最少、配送總費用最低、配送總時間最少、使用的配送車輛數最少、配送車輛的滿載率最高等。

1.2.2 配送車輛優化調度問題的構成要素

配送車輛優化調度問題主要包括貨物、車輛、配送中心、客戶、運輸網絡、約束條件和目標函數等要素。

1.貨物

貨物是配送的對象。可將每個客戶需求（或供應）的貨物看成一批貨物。每批貨物都包括品名、包裝、重量、體積、要求送到（或取走）的時間和地點、能否分批配送等屬性。

貨物的品名和包裝，是選用配送車輛的類型以及決定該批貨物能否與其他貨物裝在同一車輛內的依據。例如，一些貨物因性質特殊需要使用專用車輛裝運；一些貨物因性質特殊不能與其他貨物裝在同一車輛內；一些貨物雖然性質特殊，但由于包裝條件很好，故也能與其他貨物裝在同一車輛內。

貨物的重量和體積是進行車輛裝載決策的依據。當某個客戶需求（或供應）貨物的重量或體積超過配送車輛的最大裝載重量或容積時，則該客戶將需要多臺車輛進行配送。

貨物的送到（或取走）時間和地點是制定車輛的出行時間和配送路線的依據。

允許貨物分批配送，是指某個客戶的需求（或供應）的貨物可以用多輛車分批送到（或取走），即使其需求（或供應）量在一輛車的裝載量以下。

2.車輛

車輛是貨物的運載工具，其主要屬性包括：車輛的類型、裝載量、一次配送的最大行駛距離、配送前的停放位置及完成任務后的停放位置等。

車輛的類型有通用車輛和專用車輛之分，通用車輛適于裝運大多數普通貨物，專用車輛適于裝運一些性質特殊的貨物。

車輛的裝載量是指車輛的最大裝載重量和最大裝載容積，是進行車輛裝載決策的依據。在某配送系統中，車輛的裝載量可以相同，也可以不同。

對每臺車輛一次配送的行駛距離的要求可分為以下幾種情況：

① 無距離限制；

② 有距離限制；

③ 有距離限制，但可以不遵守，只是不遵守時需另付加班費。

車輛在配送前的停放位置可以在某個停車場、配送中心或客戶所在地。

車輛完成配送任務后，對其停放位置的要求可分為以下幾種情況：

① 必須返回出發點；

② 必須返回某停車場；

③ 可返回到任意停車場；

④ 可停放在任何停車場、配送中心或客戶所在地。

3.配送中心

配送中心是進行集貨、分貨、配貨、配裝、送貨作業的地點，也可指具有相似功能的物流中心、倉庫、車站、港口等。

在某配送系統中，配送中心的數量可以只有一個，也可以有一個以上；配送中心的位置可以是確定的，也可以是不確定的。對于某個配送中心，其供應的貨物可能有一種，也可能有多種；其供應的貨物數量可能能夠滿足全部客戶的需求，也可能僅能滿足部分客戶的需求。

4.客戶

客戶也稱為用戶，包括分倉庫、零售商店等。客戶的屬性包括需求（或供應）貨物的數量、需求（或供應）貨物的時間、需求（或供應）貨物的次數及需求（或供應）貨物的滿足程度等。

在某個配送系統中，某個客戶的需求（或供應）貨物的數量可能大于車輛的最大裝載量，也可能小于車輛的最大裝載量；而該系統全部客戶的貨物需求（或供應）總量可能超過全部車輛的總裝載量，也可能低于全部車輛的總裝載量。

某客戶的需求（或供應）貨物的時間，是指要求將貨物送到（或取走）的時間，對配送時間的要求可分為以下幾種情況：

① 無時間限制；

② 要求在指定的時間區間（也稱為時間窗）內完成運輸任務；

③ 有時間限制，但可以不遵守，只是不遵守時要給予一定的懲罰。

某客戶的需求（或供應）貨物的次數可能僅有一次，即只需一次配送服務；也可能為多次，即需要多次配送服務。

某客戶對需求（或供應）貨物的滿足程度的要求可分為兩種情況：

① 要求全部滿足；

② 可以部分滿足，但不滿足時要受到懲罰。

5.運輸網絡

運輸網絡是由頂點（指配送中心、客戶、停車場）、無向邊和有向弧組成的。邊、弧的屬性包括方向、權值和交通流量限制等。

某運輸網絡中可能僅有無向邊；也可能僅有有向弧；還可能既有無向邊，又有有向弧。

運輸網絡中邊或弧的權值可以表示距離、時間或費用。邊或弧的權值變化分為以下幾種情況：

① 固定，即不隨時間和車輛的不同而變化；

② 隨時間不同而變化；

③ 隨車輛的不同而變化；

④ 既隨時間不同而變化，又隨車輛不同而變化。對運輸網絡權值間的關系可以要求其滿足三角不等式，即兩邊之和大于第三邊；也可以不加限制。

對運輸網絡中頂點、邊或弧的交通流量要求分為以下幾種情況：

① 無流量限制；

② 邊、弧限制，即每條邊、弧上同時行駛的車輛數有限；

③ 頂點限制，即每個頂點上同時裝、卸貨的車輛數有限；

④ 邊、弧、頂點都有限制。

6.約束條件

配送車輛優化調度問題應滿足的約束條件主要包括：

① 滿足所有客戶對貨物品種、規格、數量的要求。

② 滿足客戶對貨物發到時間范圍的要求。

③ 在允許通行的時間進行配送（如有時規定白天不能通行貨車等）。

④ 車輛在配送過程中的實際載貨量不得超過車輛的最大允許裝載量。

⑤ 在配送中心現有運力范圍內。

7.目標函數

對配送車輛優化調度問題，可以只選用一個目標，也可以選用多個目標。經常選用的目標函數主要有以下幾個。

① 配送總里程最短。配送里程與配送車輛的耗油量、磨損程度以及司機疲勞程度等直接相關，它直接決定運輸的成本，對配送業務的經濟效益有很大影響。由于配送里程計算簡便，它是確定配送路線時用得最多的指標。

② 配送車輛的噸位公里數最少。該目標將配送距離與車輛的載重量結合起來考慮，即以所有配送車輛的噸位數（最大載重噸數）與其行駛距離的乘積的總和最少為目標。

③ 綜合費用最低。降低綜合費用是實現配送業務經濟效益的基本要求。在配送中，與取送貨有關的費用包括：車輛維護和行駛費用、車隊管理費用、貨物裝卸費用、有關人員工資費用等。

④ 準時性最高。由于客戶對交貨時間有較嚴格的要求，為提高配送服務質量，有時需要將準時性最高作為確定配送路線的目標。

⑤ 運力利用最合理。該目標要求使用的較少的車輛完成配送任務，并使車輛的滿載率最高，以充分利用車輛的裝載能力。

⑥ 勞動消耗最低。即以司機人數最少、司機工作時間最短為目標。

1.2.3 配送車輛優化調度問題的分類

配送車輛優化調度問題可按照其構成要素劃分為不同的種類。

（1）按配送中心的數目分，有單配送中心問題（配送系統中僅有一個配送中心）和多配送中心問題（配送系統中存在多個配送中心）。

（2）按車輛載貨狀況分，有滿載問題（由于客戶需求或供應的貨物數量大于或等于車輛的載重量，故完成一項配送任務需要一輛或多輛配送車輛，配送車輛需要滿載運行）、非滿載問題（由于客戶需求或供應的貨物數量小于車輛載重量，多項配送任務可共用一輛配送車輛，車輛在配送過程中經常處于不滿載狀態）以及滿載和非滿載混合問題（由于一部分客戶需求或供應的貨物數量大于或等于車輛的載重量，而另一部分客戶需求或供應的貨物數量小于車輛的載重量，造成一些配送車輛需要滿載運行，而另一些車輛則經常處于不滿載狀態）。

（3）按配送任務特征分，有純送貨問題（僅考慮從配送中心向客戶送貨，也稱為純卸問題）或純取貨問題（僅考慮把各客戶供應的貨物取到配送中心，也稱為純裝問題）及取送混合問題（既考慮將客戶需求的貨物從配送中心送到各個客戶，同時也考慮將客戶供應的貨物從客戶取到配送中心，也稱為裝卸混合問題或集貨和送貨一體化問題）。為了便于敘述，本書將純送貨或純取貨的配送車輛優化調度問題稱為單向配送車輛優化調度問題，而將取送混合的配送車輛優化調度問題稱為雙向配送車輛優化調度問題。

（4）按客戶對貨物取（送）時間的要求分，有無時限問題（客戶對貨物的取走或送到的時間無具體要求）和有時限問題（客戶要求將需求的貨物在規定的時間窗內送到，將供應的貨物在規定的時間窗內取走，也稱為有時間窗問題）。有時限問題又可以分為硬時間窗問題（客戶要求貨物必須在規定的時間窗內送到或取走，不能提前也不能拖后）和軟時間窗問題（客戶要求將貨物盡量在規定的時間窗內送到或取走，但也可以提前或拖后，只不過在提前或拖后時，要對配送企業實施一定的懲罰）。

（5）按車輛類型數分，有單車型問題（所有配送車輛的載重量相同）和多車型問題（配送車輛的載重量不完全相同）。

（6）按車輛對車場的所屬關系分，有車輛開放問題（即車輛完成配送任務后可以不返回其發出車場）和車輛封閉問題（車輛完成配送任務后必須返回其發出車場）。

（7）按優化目標數分，有單目標問題（僅考慮一個配送目標）和多目標問題（同時考慮多個配送目標）。

（8）按客戶、車輛、運輸網絡等的屬性信息是否確定，可分為靜態問題（客戶、車輛和運輸網絡的屬性全部已知且固定）和動態問題（客戶、車輛或運輸網絡的屬性中，有的信息未知或會發生變化）。

1.2.4 對本書所研究的配送車輛優化調度問題的界定

如1.2.2節所述，現實中的配送車輛優化調度問題是十分復雜的，為了方便建模和求解，需要對現實問題進行一些抽象和簡化。現對本書研究的配送車輛優化調度問題做如下界定。

（1）從一個或多個配送中心向多個客戶送貨（或取貨、或既送貨又取貨）；配送中心和客戶的位置一定；配送中心供應的貨物能夠滿足所有客戶的需求。

（2）各個客戶需求（或供應）的貨物均可以相互混裝，即可以裝在同一配送車輛內；每個客戶的貨物需求量（或供應量）不超過配送車輛的最大載重量；每個客戶的送貨（或取貨）要求必須滿足，且僅能由一臺車輛完成，不允許分批配送。

（3）每臺配送車輛的最大載重量一定，不允許超載；每臺配送車輛一次配送的最大行駛距離一定，不允許超過；配送時，設每臺車輛都從配送中心出發，向一些客戶提供配送服務后，最終返回配送中心。

（4）對于客戶要求將需求（或供應）貨物送到（或取走）的時間，分別考慮以下三種情況：

① 無時間限制；

② 要求在指定的時間窗內完成送貨（或取貨）任務，不允許提前或拖后；

③ 有時間限制，但可以不遵守，只是不遵守時要對配送企業給予一定的懲罰。

（5）配送中心與客戶之間以及客戶相互之間的最短距離已知且固定；配送車輛在配送中心、客戶間的行駛時間已知且固定；不考慮運輸網絡中車輛流量的限制。

根據以上界定，本書所研究的配送車輛優化調度問題均屬于非滿載且車輛封閉的車輛調度問題。在上述界定的基礎上，本書將具體研究以下幾類配送車輛優化調度問題。

1. 單配送中心車輛優化調度問題

具體包括：

（1）無時限單向配送車輛優化調度問題；

（2）有時限單向配送車輛優化調度問題，又分為硬時間窗單向配送車輛優化調度問題和軟時間窗單向配送車輛優化調度問題；

（3）無時限雙向配送車輛優化調度問題；

（4）有時限雙向配送車輛優化調度問題，又分為硬時間窗雙向配送車輛優化調度問題和軟時間窗雙向配送車輛優化調度問題。

2.多配送中心車輛優化調度問題

具體包括：

（1）無時限多配送中心車輛優化調度問題；

（2）有時限多配送中心車輛優化調度問題。

3.動態配送車輛優化調度問題

具體包括：

（1）動態車輛配送優化調度問題；

（2）動態網絡配送車輛優化調度問題。