配送是物流系统的一个重要环节,而配送业务中,配送车辆调度问题的涉及面广,是配送系统优化的关键。

物流配送车辆调度问题可以描述为:在一个存在供求关系的系统中，有若干台车辆、若干个物流中心和客户，要求合理安排车辆的行车路线和出行时间，从而在给定的约束条件下，把客户需求的货物从物流中心送到客户，把客户供应的货物从客户取到物流中心，并使目标函数取得优化。

物流配送车辆调度问题的一般性定义是：物流配送车辆调度问题是把一系列的装货点和（或）卸货点，有机的组织起来，形成一系列行车线路，使待调度车辆能够高效、节能且有序地通过这些点。

当然，这种组织方式是应该在满足一定的约束条件（例如：用户对货物的需求量、一次性发货量、应交发货时间、单个车场的车辆容量限制、路程约束、时间限制等），最终达到缩短里程、减少开支费用、缩短运输时间、使用车辆数尽量少等优化目标。

物流配送车辆调度问题一般研究的是在配送中心及用户位置均已知、资源及运输能力充分、各用户需求量己知的前提下，如何合理、高效、低成本的解决分配与运送的问题，也就是说如何将货物从配送中心按照一定的要求发送到若干个用户点。

第二节车辆调度问题的构成要素物流配送车辆调度问题主要包括货物，车辆，物流中心，客户，运输网络，约束条件和目标函数等要素。

（1）货物货物是配送的对象。

可将每个客户需求(或供应)的货物看成一批货物。

每批货物都包括品名、包装、重量、体积、要求送到(或取走)的时间和地点、能否分批配送等属性。

（2）车辆车辆是“车”与车的单位“辆”的总称。

所谓车，是指陆地上用轮子转动的交通工具；所谓辆，来源于古代对车的计量方法。

本文所说的车辆是指运载货物的工具，车辆的主要属性包括：类型、工作时间、配送前的停放位置、载重量以及配送任务完成后的停放位置等。

（3）物流中心也称为物流基地、物流据点，是指进行集货、分货、配货、配装、送货作业的配送中心、仓库、车站、港口等。

在某配送系统中，物流中心的数量可以只有一个，也可以有一个以上;物流中心的位置可以是确定的，也可以是不确定的。

对于某个物流中心，其供应的货物可能有一种，也可能有多种;其供应的货物数量可能能够满足全部客户的需求，也可能仅能满足部分客户的需求。

（4）客户也称为用户，指的是物流配送的服务对象。

可以是各种零售店，也可以是分仓库，还可以是别的仓库的外调。

也就是说客户是有配送任务的对象的统称。

客户的属性包括需求(或供应)货物的数量、需求(或供应)货物的时间、需求(或供应)货物的次数及需求(或供应)货物的满足程度等。

（5）运输网络运输网络是由顶点(指物流中心、客户、停车场)、无向边和有向弧组成的。

边、弧的属性包括方向、权值和交通流量限制等。

某运输网络中可能仅有无向边;也可能仅有有向弧;还可能既有无向边，又有有向弧。

运输网络中边或弧的权值可以表示距离、时间或费用。

边或弧的权值变化分为以下几种情况:①固定，即不随时间和车辆的不同而变化;②随时间不同而变化;③随车辆的不同而变化;④既随时间不同而变化，又随车辆不同而变化。

对运输网络权值间的关系可以要求其满足三角不等式，即两边之和大于第三边;也可以不加限制。

对运输网络中顶点、边或弧的交通流量要求分为以下几种情况:①无流量限制:②边、弧限制，即每条边、弧上同时行驶的车辆数有限:③顶点限制，即每个顶点上同时装、卸货的车辆数有限;④边、弧、顶点都有限制。

（6）约束条件物流配送车辆调度问题应满足的约束条件主要包括：①满足所有客户对货物品种、规格、数量的要求；②满足客户对货物发到时间范围的要求；③在允许通行的时间进行配送(如有时规定白天不能通行货车等)；④车辆在配送过程中的实际载货量不得超过车辆的最大允许装载量；⑤在物流中心现有运力范围内。

（7）目标函数目标函数是指所关心的目标(某一变量)与相关的因素(某些变量)的函数关系。

简单的说，就是你求解后所得出的那个函数。

在求解前函数是未知的，按照你的思路将已知条件利用起来，去求解未知量的函数关系式，即为目标函数。

本课题研究的物流配送车辆调度问题，可以只选用一个目标，也可以同时选用多个目标。

经常选用的目标函数主要有：①配送总里程最短。

配送里程与配送车辆的耗油量、磨损程度以及司机疲劳程度等直接相关，它直接决定运输的成本，对配送业务的经济效益有很大影响。

由于配送里程计算简便，它是确定配送路线时用得最多的指标。

②配送车辆的吨位公里数最少。

该目标将配送距离与车辆的载重量结合起来考虑，即以所有配送车辆的吨位数(最大载重吨)与其行驶距离的乘积的总和最少为目标。

③综合费用最低。

降低综合费用是实现配送业务经济效益的基本要求。

在物流配送中，与取送货有关的费用包括:车辆维护和行驶费用、车队管理费用、货物装卸费用、有关人员工资费用等。

④准时性最高。

由于客户对交货时间有较严格的要求，为提高配送服务质量，有时需要将准时性最高作为确定配送路线的目标。

⑤运力利用最合理。

该目标要求使用的较少的车辆完成配送任务，并使车辆的满载率最高，以充分利用车辆的装载能力。

⑥劳动消耗最低。

即以司机人数最少、司机工作时间最短为目标。

第三节车辆调度问题的分类物流配送车辆调度问题可按照其构成要素划分为不同的种类。

(1)按物流中心的数目分，有单物流中心问题(配送系统中仅有一个物流中心)和多物流中心问题(配送系统中存在多个物流中心)。

(2)按车辆载货状况分，有满载问题(由于客户需求或供应的货物数量大于或等于车辆的载重量，故完成一项配送任务需要一辆及其以上的配送车辆，配送车辆需要满载运行)、非满载问题(由于客户需求或供应的货物数量小于车辆载重量，多项配送任务可共用一辆配送车辆，车辆在配送过程中经常处于不满载状态)以及满载和非满载混合问题(由于一部分客户需求或供应的货物数量大于或等于车辆的载重量，而另一部分客户需求或供应的货物数量小于车辆的载重量，造成一些配送车辆需要满载运行，而另一些车辆则经常处于不满载状态)。

(3)按配送任务特征分，有纯送货问题(仅考虑从物流中心向客户送货，也称为纯卸问题)或纯取货问题(仅考虑把各客户供应的货物取到物流中心，也称为纯装问题)及取送混合问题(既考虑将客户需求的货物从物流中心送到各个客户，时考虑将客户供应的货物从客户取到物流中心，也称为装卸混合问题或集货和送货一体化问题)。

为了便于叙述，本文将纯送货或纯取货的物流配送车辆调度问题称为单向物流配送车辆调度问题，而将取送混合的物流配送车辆调度问题称为双向物流配送车辆调度问题。

(4)按客户对货物取(送)时间的要求分，有无时限问题(客户对货物的取走或送到的时间无具体要求)和有时限问题(客户要求将需求的货物在规定的时间窗内送到，将供应的货物在规定的时间窗内取走，也称为有时间窗问题)。

有时限问题又可以分为硬时间窗问题(客户要求货物必须在规定的时间窗内送到或取走，不能提前也不能拖后)和软时间窗问题(客户要求将货物尽量在规定的时间窗内送到或取走，但也可以提前或拖后，只不过在提前或拖后时，要对配送企业实施一定的惩罚)。

(5)按车辆对车场的所属关系分，有车辆开放问题(即车辆完成配送任务后可以不返回其发出车场)和车辆封闭问题(车辆完成配送任务后必须返回其发出车场)。

(6)按车辆类型数分，有单车型问题(所有配送车辆的载重量相同)和多车型问题(配送车辆的载重量不完全相同)。

(7)按优化目标数分，有单目标问题(仅考虑一个配送目标)和多目标问题(同时考虑多个配送目标)。

第四节车辆调度问题的最优化算法车辆调度的基本问题有运输问题，旅行商问题，分派问题，背包问题，最短路问题，中国邮路问题等，常用的基本方法有线性规划法，分支定界法，切平面法，动态规划法(1)表上作业法(Tabular method)是求解运输问题的一种简便而有效的方法，是一个非常成熟的算法，由Charners与Coopert954年提出，尽管它不是一种多项式算法，但广泛见诸于各类专著和教科书中，且有着良好的应用基础。

其求解工作在运输表上进行。

它的条件是问题求最小值，产销平衡和运价非负。

它是一种迭代法，迭代步骤为：先按某种规则找出一个初始解（初始调运方案）；再对现行解作最优性判别；若这个解不是最优解，就在运输表上对它进行调整改进，得出一个新解；再判别，再改进；直至得到运输问题的最优解为止。

适用于求解小规模问题。

(2)分枝定界法(Branch and hound)是一种隐枚举法或部分枚举法，它不是一种有效算法，是枚举法基础上的改进，是求解整数规划的较好方法。

Held和Karp指出分枝定界法的求解效率与其界限设定的宽紧有极大的关系，所以分枝定界法比较适用于求解小型问题。

(3)切平面法(Cutting planes)与分枝定界法类似，也是在求解与整数规划相对应的线性规划上，不断地增加新的约束，也就是另外加入线性约束条件，以切掉对应于非整数规划的所有可行解的集合，以使问题可达到整数线性规划求解的形式,从而获得最优解。

求解时间过长，不适用于大规模问题。

(4)动态规划算法(Dynamic programming)是Kolen等在1987年提出的，解题的基本思路是将一个n阶段的决策问题转化为依次求解n个具有递推关系的单阶段的决策问题,从而简化计算过程。

因其复杂性在于各阶段决策之间的相互联系,而且计算时间与计算机内存空间均随变量的增加而里指数增加。

所以虽然此方法可求得最优解，但仅适用于较小规模的最优问题。