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）动态网络配送车辆优化调度问题。