物流配送车辆调度路径优化问题算法研究

       文章编号：1002-3100(2015)03-0005-04

       0 引言

       由国家发展和改革委员会、国家统计局和中国物流与采购联合会2014年3月7日联合发布的《2013年全国物流运行情况通报》[1]显示，2013年中国社会物流总费用10.2万亿元，同比增长9.3％，与GDP的比率为18％。这一比率远高于美国的8.5％，日本的8.7％和德国的8.3％，高于全球平均水平约6.5个百分点。这些数据反映出中国物流成本偏高的现状。物流总费用中运输费用5.4万亿元，同比增长9.2％，占社会物流总费用的比重为52.5％。同时，2013年中国物流业增加值3.9万亿元，同比增长8.5％。可以看出，全社会物流企业收入增速低于物流费用增速，物流企业普遍盈利能力偏低。报告总结性的指出，2013年，我国物流运行总体平稳，物流需求规模保持较高增幅，物流业增加值平稳增长，但经济运行中的物流成本依然较高。

       随着人们对环境问题给予越来越多的关注，关于要求企业保护环境的法律条文相继增加。其中，减少废物的排放量和能源的消耗成为法律规定的两个重要内容。物流作为一个与环境关系密切的行业，车辆调度配送路径优化问题同时涉及能源消耗和废物的排放问题，因而其一直是国内外研究的热点。

       综上所述，作为继原材料、劳动力以外的“第三利润源泉”，实现物流合理化具有重要的经济意义与现实意义。一方面，物流配送车辆路径优化有助于企业降低物流成本，提高运作效率，从而增加企业利润。另一方面，通过缓解交通压力，减少资源消耗和对环境的污染真正做到环保物流。

       1 车辆调度问题描述

       物流配送车辆路径优化问题最早是由线性规划之父Dantzig和Ramser[2]在1959年提出，该问题是交通运输管理、智能救灾调度指挥系统、网络作业调度管理系统、现代物流系统、物流网等应用、研究领域中的基本问题之一，也是最重要的调度问题之一。

       配送车辆调度问题要解决的问题[3]是车辆从配送中心(这里的配送中心是个广义概念，指的是车辆的出发地，包括物流中心、配送中心、仓库、车场等)出发去完成一些配送任务，当各任务量较小(小于车辆容量)时，为了提高车辆的利用率，可安排一辆车执行几项运输任务。这时，如何安排车辆的路线，使得既满足各任务的需求并完成任务，而又使总成本最小(这里的总成本指的是一个广义概念，包括时间最少、运营费用最少等)涉及的就是配送车辆路径优化问题。

       在学术研究方面一般把这个问题抽象解释为路线安排问题或者车辆路径问题(Vehicle Routing Problem，VRP)，可描述如下：有一个或几个配送中心(i=1，2，…，n)，每个配送中心有K种不同的车型，每种车型有n量车。有一批配送业务(i=1，2，…，n)，已知每个配送业务的需求量(i=1，2，…，n)，要求在一定的时间范围内[]完成，求在满足不超过配送车辆载重量等的约束条件下，安排配送车辆在合适的时间及最优路线等约束条件下总成本最小。

       2 VRP的构成要素分析

       配送车辆调度问题主要包括道路、货物、车辆、物流中心、客户、运输网络、约束条件和目标函数等要素。VRP问题主要是以下几个因素的多个组合[4]：(1)道路。道路是货物运输的基础，也是构成VRP的核心要素之一。通常用从中心仓库出发按照一定的路线依次经过各个客户点，最后返回配送中心所形成的网络图表示。(2)货物。货物是配送的对象，包括品名、包装、重量、体积、要求送到(或取走)的时间和地点、能否分批配送等属性。(3)车辆。车辆是货物的运载工具。其主要属性包括车辆的类型、转载量、一次配送的最大行驶距离、配送前的停放位置及完成任务的停放位置等。(4)物流中心。也称为物流基地、物流据点，是指进行集货、分货、配货、送货作业的配送中心、仓库、车站、港口等。(5)客户。也称为用户，包括分仓库、零售商店等。客户的属性包括需求(或供应)货物的数量、需求(或供应)货物的时间、需求(或供应)货物的次数及需求(或供应)货物的满足程度等。(6)运输网络。运输网络由顶点(指物流中心、客户、停车场)、无向边和有向弧组成。边、弧的属性包括方向、权值和交通流量限制等。(7)约束条件。配送车辆调度问题应满足的约束条件主要包括：①在允许通行的时间进行配送。②在物流中心现有运行能力范围内等。③满足客户对货物发到时间范围的要求。④满足所有客户对货物品种、规格、数量的要求。⑤车辆在配送过程中的实际载货量不得超过车辆的最大允许装载量。(8)目标函数。配送车辆调度问题可以只选用一个目标，也可以选用多个目标。经常选用的目标函数主要有：①最大化准时性。②最小化劳动消耗。③最大化运力利用。④最小化综合费用。⑤最小化配送总里程。⑥最小化配送车辆的吨位公里数。