内容提要：对单车线路优化问题进行重点阐述。求解过程采用了最节约插值法与混合遗传算法，较好地解决了单车配送线路优化问题。通过实例数据测试，表明两种算法的结合优化效果显著。

好地解决了单车配送线路优化问题。通过实例数据测试，表明两种算法的结合优化效果显著。

关键词：物流配送，车辆路线问题，最节约插值法，混合遗传算法

1概述

当前，企业物流配送决策支持信息系统的研究开发与应用已成为热点和难点问题。据笔者调研，目前国内绝大多数对物流配送的车辆路线问题（VRP：Vehicle Routing Problem）的研究都是建立在假设的抽象网络图上，而不是基于真实的城市街道环境。虽然在研究中，真实的城市街道网络最终要抽象为网络拓扑图，但在转换过程中往往会丢失一些有用信息，这些信息往往与具体环境相关并且很有可能恰恰是企业所关心的。相比车辆线路优化问题对企业所具有的重大意义和国外的研究状况而言，我国对配送线路优化问题的研究还远远不够，国内车辆线路优化调度的研究目前大多停留在理论层次上，实际应用系统开发才刚起步，计算机配送车辆优化调度系统的成功应用鲜见报导。因此，从国内的真实城市街道环境和现状出发，结合企业实际进行针对性研究，探索和开发适合我国城市配送的车辆调度软件，具有明显的现实意义。

浙江省烟草公司杭州分公司（杭烟）在杭州城区共有6400多家卷烟零售户，公司所属物流配送中心备有20多辆送货面包车，共有120多条不同送货线路。目前杭烟的零售客户分布在城区的各个大街小巷，地理位置非常分散，而且物流配送中心位于市郊，与网点距离较远，这种布局存在两个方面的问题：①访销线路是各访销部自己通过访销线路人工确定的，没有从整体上进行优化，配送成本较高；②配送线路是根据访销线路确定的，不同配送线路之间工作量存在较大差距，影响了物流配送服务质量的提高。为此杭烟管理层及时提出配送车辆线路优化调度课题的研究工作，采用一种科学和可行的方法来对不同配送线路进行工作量和成本的考核。

本文在参考大量中外文献基础上，以杭烟配送车辆线路优化调度课题为研究背景，对基于城市街道的较大规模单车配送线路优化问题进行了深入的研究。由于VRP是强NP难题，决定了大规模情况下对其精确求解不现实，为此，笔者在对现有VRP算法归类分析和对企业实际要求提炼基础上，考虑城市街道中方向性等具体因素，将问题拆分为线路划分和单车线路优化两个步骤分别进行求解，即采取“合而分之，各个击破”的策略，先进行配送线路划分，然后在划分基础上进行单车线路优化，较好地解决了大规模配送条件下要在可行时间内求得优化解或满意解的问题。

2基于城市街道的单车配送线路优化问题求解

对有6400多个网点的这样一个大规模VRP问题，采用直接求解是不现实的，很难在可行时间内得到满意的车辆调度结果。在系统实际运行时，只需在一段时间内（如一年）线路划分工作完成后，以后每天每次每辆车的VRP问题就成为求解相对简单的N个较小规模的单车线路优化问题了。

对于单车送货线路的求解，笔者首先提出任意两个网点间经济距离的概念，然后建立单车送货线路的系统模型，采用最节约插值法和混合遗传算法分别对此模型进行求解，进行实验数据的计算机仿真，最后在基于地理信息系统（GIS，Geography Information System）平台下进行单车线路的配送车辆优化调度应用工作。求解过程采用了最节约插值法与混合遗传算法，较好地解决了单车配送线路优化问题。通过实例数据测试，表明两种算法的结合，优化效果明显。

2.1零售网点间的最短经济距离

2.1.1经济距离界定

在实际的物流配送中，影响司机选择行车路径的因素有很多，除了行车时间和行车距离外，其它因素如街道的路面质量、通畅程度、红绿灯的多少等也会影响司机的路径选择。这意味着单纯用距离或行车时间来确定最短线路并不很符合现实情况，这两种情况下的最短路径并不等于行车线路的最优。正是基于这个考虑，为了使模型能更接近实际，本文使用了经济距离的概念。