基于节约算法的车辆路径问题研究

张颐颖

[摘 要]车辆路径问题是物流配送中的决策难题，配送成本的减少成为优化的主要目的，而科学家们对车辆调度优化采用的方法层出不穷。本文针对节约算法做了简单的概述与研究，并以飞马快运公司为例，采用节约算法对该公司的车辆调度进行简单的调整。

[关键词]车辆调度；路径优化；节约算法

[中图分类号]F224 [文献标识码]A [文章编号]1005-6432（2014）27-0130-02

1 背 景

在物流配送领域，配送成本费用是配送运输成本、分拣成本、配装成本以及流通加工成本的总和。配送运输成本是成本费用中较大开支，尤其是配送点多、路线较长时，配送路径的选择直接决定运输成本的大小。因此，在配送点及配送点需求量已知的情况下，如何通过科学的方法选择最优路径是物流配送中最关键的抉择[1]。

车辆路径问题（Vehicle Routing Problem，简称 VRP）[2]，又称为车辆调度问题，通常是在配送中心及配送点之间，选择适当的路线，使车辆有序地通过，在满足一定的约束条件（如货物需求量、发送量、交货时间、车辆容量限制、行驶里程限制、时间限制等）下，达到一定的目标（如路程最短、费用最少、时间尽量少、使用车辆数尽量少等），并返回配送中心。

配送车辆路径问题是世界公认的 NP 难题，国内外很多学者都进行了研究，并提出了多种路线选择及路径优化方法。本文采用了节约算法对飞马公司的车辆调度问题进行研究与分析。

2 案例分析

飞马快运是依托邯运集团邯郸汽车客运网络发展起来的快递企业，2005年成立，主要开展无人跟随的小件快递业务。目前客运网络日发班车1838次，营运线路126条，营运里程13107公里，沿途经过站点1270个，班车辐射16个省市、78个大中城市，联系晋冀鲁豫四省的经济文化中心。目前的服务项目有同城快递、省内外货物快递、零担货物快递，包装服务、对方付费、代收货款，上门接货、送货上门、仓储分拣，货物到达、受理一条龙服务，异地货物中转、异地货物派送上门，代购亲情速递物品，箱式专线运输等。

飞马快运承运的货物主要放在客车底舱随车运输。邯郸客运网络能覆盖的地区，由该客运网络的班车运输。该客运网络不能覆盖的地区，与其他省市的运输公司合作，由合作的运输公司代为送达。目前，飞马快运与省内外50余家汽车站、企业以及个体配货点建立了业务合作关系。同时，公司现拥有130多部1.5吨以下厢式货车，其中邯郸客运总站内停17部，其余116部车平时分布在邯郸市内各业务网点，包括商场、批发点等。这116部货车主要负责市内配送业务，同时提供上门取货业务、送货业务，不提供长途运输业务。站内17部货车可以提供出省运输业务。至今，飞马快运的服务范围包括：同城快递，市内所有区、街、巷及市郊各县（市），省内快递含河北省所有地、市、县，全国快运含北京、天津、上海、辽宁、河北、河南、山西、山东、陕西、江苏、江西、湖南、湖北、浙江等省市。货运起步价90元，每公里2.5元。

在本案例中，主要研究邯郸客运站的发车量以及发车的路径，针对不同的路径做调整，以达到运输成本最低。邯郸客运站可以看作是一个配送中心，研究由该配送中心负责整个配送网络客户需求的车辆调度问题，正常情况下由客户提前提出需求计划（包含需求量和需求时间）后，由配送中心负责配送。而配送中心考虑到自身运营成本的因素，采用循环式配货方式对多个需求客户配送。

3 研究方法

3.1 节约算法简述

本文采用了节约算法。节约算法是由 Clarke 和 Wright 提出的一种经典启发式算法，节约法求解路线安排问题采用的是典型的启发式思路。首先，以所有配送点均采用直接往返的送貨作为初始的可行安排。计算每两个配送点连接带来的节约量，按节约量由大到小的顺序，寻找节约量最大的两个配送点：①如果它们连接后，所在线路上的货运量之和不超过车辆的载重限制，连接这两个配送点；并进一步寻找与这两个配送点进行连接带来节约量最大的配送点，把这个配送点也连接到这条线路上，直到该线路上的所有配送点的货运量之和等于或超过车辆的载重限制，连接使总货运量超过车辆载重的最后一个配送点，本线路为该配送点提供的货运量刚好使车辆满载。②如果它们连接后，所在线路上的货运量之和等于车辆的载重限制，连接这两个配送点。③如果它们连接后，所在线路上的货运量之和超过车辆的载重限制，连接这两个配送点，并使车辆刚好满载。将剩余的配送点和配送向量组成一个新的配送线路规划问题，重复采用上述方法，直到所有可能连接的配送点全部连接完成后，结果作为路线安排的最优解[3]。

3.2 节约算法具体应用

3.2.1 模型的建立

3.2.2 节约算法的步骤

1）取最大节约值1012，即天津到廊坊，此时载重量为1.2t，不能再增加一个地方的载重量。

2）除去到天津与廊坊的节约值，在剩余的节约值中取最大值658，即北京到沧州，此时载重量为1.2t，也不能再增加一个地方的载重量。

3）在前面的基础上再挑选最大节约值391，即衡水到保定，此时载重量为0.8t，剩余的节约值为349，石家庄到衡水，载重量变成1.4t。

4）7个地区都有路线经过，即得到路线的最小值，也就是从邯郸派三辆车，路径分别为：邯郸——天津——廊坊——邯郸；邯郸——北京——沧州——邯郸；邯郸——石家庄——衡水——保定——邯郸。

4 优化方案

通过应用节约算法讨论该问题，最后得出的结果为：邯郸应该派三辆车，分别派往邯郸——天津——廊坊——邯郸，载重量为1.2t，运费为1700元；邯郸——北京——沧州——邯郸，载重量为1.2t，运费为1665元；邯郸——石家庄——衡水——保定——邯郸，载重量为1.4t，运费为1132.5元。最后得出的总运费为4497.5元。因此该公司可以根据本文中提供的方法解决该问题。

5 结 论

本文通过分析研究实际生活中存在的问题，通过运用节约算法提出解决方法。C-W节约算法思想简单，在解决旅行商问题时是一种很好的算法，可以快速得到问题的满意解。

参考文献：

[1]范洁，曹俊琴.改进节约算法在电表配送路线选择中的应用[J].物流工程与管理，2012，34（214）：102-105.

[2]Dantzing G，Ramser J.The truck dispatching problem[J].Management Science，1959，10（6）：80-91.

[3]张学志，陈功玉.车辆路线安排的改进节约算法[J].系统工程，2008，26（11）：67-70.