物流运输中多车型配送车辆的调度模型

配送车辆调度问题是运筹学和组合优化领域的热点问题.多车型配送车辆调度问题是配送车辆调度问题的一个分支，一般情况下，配送企业为了适应配送商品种类繁多、性质各异、客户要求各不相同的情况，往往配置多种类型的配送车辆，以提高车辆的满载率，降低配送成本.可见，研究多车型配送车辆调度问题具有重要的理论和现实意义.

本文在现有研究成果的基础上，建立了多车型配送车辆调度问题的基于直观描述的数学模型，考虑的目标函数和约束条件比较接近实际，决策变量、目标函数和约束条件的表示较为自然、直观和易于理解.

1.对多车型配送车辆调度问题的描述

现实中的多车型配送车辆调度问题十分复杂，为了方便建模和求解，需要对现实问题进行一些抽象和简化.现对本文研究的多车型配送车辆调度问题作如下描述：

1）从一个配送中心向多个客户送货，配送中心供应的货物能够满足所有客户的需求；

2）各个客户需求的货物均可以混装，单一客户的货物需求量不超过配送车辆的最大载重量，每个客户的送货要求必须满足，且仅能由一辆车完成，不允许分批配送；

3）配送车辆按载重量分类，每种车型的最大载重量一定且不允许超载，每种车型

的一次配送最大行驶距离一定，不允许超过.配送车辆均由配送中心出发，向一些客户提供配送服务，最后返回配送中心；

4）配送中心与客户之间及客户相互之间的最短距离已知且固定.

在满足上述条件下，我们要求运输成本最小.

2.构建数学模型

现有一个有向图G=（V，E），其中V={0，1，…，N}有N+1个顶点，E={（i，j）|i，j∈V，i≠j}表示弧集，顶点0表示配送中心，剩余的顶点集V′=V＼{0}表示N个配送点，为构建多车型最小费用车辆路径问题数学模型，定义以下参数：

gi： 配送点i的需求量；

φ={1，2，…，L}为车辆类型的集合，类型总数为L；

Kl：l车型的数量；

φl：车型l的车辆数集，φl={1，2，…，Kl}；

dij： 两个节点间的最短距离，i，j∈V；

Ql： 车型l的装载能力，Q0l表示车型l的空重；

cl： l型车每公里深圳到淮安物流每吨的载重费用，单位：元/吨・公里；

clkij： l型车的第k辆从第i点到第j点的费用，与距离和载重有关：

clkij=dijclrlkij（i，j）∈E；l∈φ；k∈φl；

rlkij： l型车的第k辆从第i点到第j点车辆的重量；

xlkij=1 l型车的第k辆从第i点行驶到第j点0 否则

式（1）表示目标函数，即总配送成本最小；

式（2）保证车辆都是从配送中心出发，最后回到配送中心；

式（3）表示进入每个货物需求点的车辆卸载后会离开；

式（4）、（5）确保每个货物需求点只能被一辆广州到南京物流车服务一次；

式（6）表示车辆承载的货物量之和不得大于车辆的容量；

式（7）是递推车辆行驶路径的总车质量；

式（8）是车辆回到配送中心时车辆的重量；

式（9）是不超过车辆的装载能力；

式（10）是经过某一配送点时车辆重量不能小于空车重量；

式（11）是l型车的第k辆从第i点到第j点的费用计算公式.

3.算法过程

在多车型低耗车辆路径问题解决过程中，本文采用爬山算法作为求解的主要算法.爬山算法是一种局部择优的方法，它采用启发式方法，是对深度优先搜索的一种改进，它利用反馈信息帮助生成解的决策.该算法每次从当前解的临近解空间中选择一个最优解作为当前解，直到达到一个局部最优解.属于人工智能算法的一种.爬山算法结构比较简单，在某些情况下，整体效率还是很好的.但它的主要缺点是有时会陷入局部最优解，而不一定能搜索到全局最优解.但由于它求解时可以把复杂问题简单化，且解的结果与最优解比较接近，所以在很多领域中都有着广泛的应用.

爬山算法的基本步骤如下：

第一步：输入多车型低耗车辆路径问题，包括配送中心、顾客点之间的坐标，配送

点需求，车型参数（载重能力、空重、不同车型固定成本）等.任意选定一个初始解x0，记录当前最优解为xbest，且令xbest=x0，令U（xbest）代表xbest的邻域.

第二步：从xbest的邻域U（xbest）中按照某一规则选出一个解xnow，转到第三步；

若当U（xbest）=φ时，或满足其他停止运算的规则时，转到第四步；

第三步：计算xnow的目标函数值minZ1，若xnow的目标函数值minZ1小于xbest的目标函数值minZ，则xbest=xnow，minZ=minZ1，U=U（xbest），转到第二步；否则 U=U-xnow，转到第二步；

第四步：输出计算结果，停止.

在爬山算法中，第一步的初始解可以采用随机方法产生，也可以用一些经验方法或者采用其他算法得到初始解.第二步中在U（xbest）中选取xnow的规则也可以采用随机选取的规则.

4.实验计算和结珠海到牡丹江物流果分析

实例：设配送中心（0，0）和16 个客户配送点分布及需求情况，具体数据见表1，假设该配送中心有3种车型，见表2.根据以上的爬山算法，我们应用Lingo语言来求解，获得费用最少的行驶路径，见表3，此时费用为3654.40元.

5.结 论

总的来说，对于复杂的VRP，如果仅凭决策者的经验，是很难在较短时间内作出一个合理的运输路径规划的，本文利用优化模型，采用爬山算法，再通过Lingo自动搜索得到费用最少的最优路径和车辆调度数.最终结果是比较令人满意的.

【参考文献】

[1]杨浩雄，胡静，何明珂.配送中多车场多任务多车型车辆调度研究[J].计算机工程与应用，2013，49（10）.

[2]钱艳婷，王鹏涛，魏国利.动态车辆路径问题的算法研究[J].天津理工大学学报，2010，26（6）.

[3]郭海湘，杨娟，等.煤矿物资多车型配送的改进遗传算法求解[J].运筹与管理，2011，20（2）.