基于GIS先验知识的智能配送优化及实现

文章编号：1003-6199(2011)04-0111-04

摘 要：物流配送作为物流产业的核心进程，其效率的高低直接影响整个物流业的发展。鉴于目前的配送调度多依赖于传统的数学模型导致规划的最优路线与实际经验不相符，文章提出将实时交通信息、行车经验等现实因素作为GIS先验知识指导智能配送的优化的算法并进行实现。应用结果表明该成果能在很大程度上提高物流配送的效率。

关键词：智能配送；遗传算法；GIS先验知识

中图分类号： P208 文献标识码：A

Optimization and Realization of the Intelligence Distribution Based on Prior Knowledge of GIS

ZHENG Xiangli

(Shenzhen Careland Technology Co., Ltd. Shenzhen 518040,China)

Abstract:As the core process of the logistics ,the efficiency of distribution will affect the development of logistics industry directly.The optimal route planning of distribution does not match to the actual experience because of much the current distribution schedule depends on traditional mathematical models.The paper proposes a algorithm that took realtime traffic information, driving experience and other practical factors as GIS prior knowledge to guide the intelligent distribution and carried out to achieve. Application results show that the research can improve the efficiency of logistics and distribution greatly.

Key words:intelligence distribution; genetic algorithms;prior knowledge of GIS

1 引 言

近年来，随着物流行业的不断发展，物流信息量迅速增加，需求的处理也越来越复杂，对配送系统的要求也越来越高，因此人们开始研究如何构建智能的物流配送系统来满足需求。目前国内研发生产的物流配送系统大多是基于各种启发式算法基础构建的VRP模型，利用这些数学模型分析配送路线，结果可能会与实际经验不完全相符，具有一定的局限性，因此应用率不高。基于此背景，在已有的导航软件研发的经验基础之上，研究将行车配送过程中的现实因素如实时交通、行车经验等信息与现有智能配送系统进行整合，建立基于GIS先验知识的智能配送系统，提高其实用价值。

2 智能配送概述

配送是物流中一种特殊的、综合的活动形式，集装卸、运输于一身，通过一系列的活动完成送货的目的。随着集约化、一体化的物流配送的发展，需将配送的各个环节综合起来，配送的核心在于集货线路优化、货物配装及送货过程的优化。

智能物流配送是指在配送规划时，运用计算机技术、图论、运筹、统计、GIS等方面的技术，根据配送的要求，由计算机自动规划出一个最佳的配送方案，包括物品的装载与车辆的调度、配送路线规划的优化等方案，旨在降低物流成本，提高客户服务水平，减轻调度人员和司机劳动强度，满足城市配送、电子商务、电话购物等现代城市物流配送业务的发展需要；以车辆最少、里程最少、运输费用最低、时间最快、满意度最高等因素为目标，把配送订单科学地分配给可用的车辆，结合配送路线的规划进行合理的装载，以完成配送任务［1］。

在实际配送过程中，由于受交通路况、客户需求、商品本身特性等条件的制约，而且各种因素又具有不确定性的特点，物流配送规划往往是一个极其复杂的系统工程［2］。目前解决这一问题的办法是将复杂问题分解或转化为一个或几个已经研究过的基本问题，如背包问题、最短路径问题、最小费用流问题等，再采用较为成熟的理论和方法进行求解，以得到智能配送问题的最优解或满意解。但是这种求解方法得到的最优解往往是理想状态下的，未能考虑现实世界的不确定因素的影响，实用性较低［3］。因此文章引入了以历史交通数据、司机行车经验信息作为样本的先验知识，再结合现今较为成熟的方法求得配送的最佳路径，最后根据规划的路径进行货物的合理装载与配送。

3 基于先验知识的智能配送的优化策略

3.1 优化原理

要实现对货物的智能配送，首先需将物流配送中心当日订单的配送信息可视化到GIS电子地图上，然后利用GIS特有的空间分析功能对客户的位置、订单数量及种类等进行分析，最后结合配送中心本身的位置、道路的交通状况以及车辆的装载能力确定配送路线。其中道路的交通状况除了道路的通达情况之外，还应考虑道路的实时通行状况。

当前实时交通信息的应用发展还不是很成熟，直接运用实时交通信息进行路线规划的可行性较小，再者此时的路线规划只是单纯的通过确定配送的路线来安排货物的装载，往往与车辆在途的实时路线规划存在差异。基于此，将历史的交通路况、司机行车经验等信息加以分析作为GIS先验知识加以运用，结合遗传算法进行配送路线的优化。

线路的规划主要考虑以下几个原则［3］：

a、 集中的原则：分布位置比较集中的客户尽量划分在一条线路上；

b、 线路最少的原则：在车辆运力允许的条件下，尽量用最少的线路进行配送；

c、 线路最短的原则：划分线路时，尽量使线路最短；

d、 行车时间最短的原则：在一定的交通状况下，保证车辆配送所花费的时间最短。

配送路线确定之后，每条路线上的客户数量、订单数量、配送商品的总体积、总重量、商品特殊性等信息也就决定了。根据这些参数和物流中心的车辆、人员状况，就可以决定装车方案。

3.2 具体的方法

智能物流配送的优化主要体现在两个方面：一是利用遗传算法实现智能配送车辆调度的优化；二是在GIS优化的遗传算法的基础上，将历史交通路况、司机行车经验、等信息作为经验知识引入。

3.2.1 遗传算法实现物流配送优化

遗传算法是通过模拟生物的遗传和进化过程而建立的一种自适应全局优化概率搜索算法，它通过模拟达尔文“优胜劣汰、适者生存”的原理鼓励产生好的结构，模仿孟德尔的遗传变异理论在算法迭代的过程中在保持原有的结构地基础上，再去寻找更好的结构而产生的［4］。其基本思想是对一组可行解个体组成的群体进行选择、交叉和变异等遗传算子的运算，产生新一代群体，并逐步使群体进化到最优解的状态。

遗传算法的运算过程：①初始化。设置进化代数计数器t=0；设置最大进化代数T；随机生成M个个体作为初始群体P(0)。②个体评价。计算群体P(t)中各个个体的适应度。③选择运算。将选择算子作用于群体。④交叉运算。将交叉算子作用于群体。⑤变异运算。将变异算子作用于群体。群体P(t)经过选择、交叉、变异运算之后得到下一代群体P(t+1)。⑥终止条件判断。若t≤T，则t=t+1，转到步骤②；若t＞T，则以进化过程中所得到的具有最大适应度的个体作为最优解输出，终止计算［5］。

利用遗传算法进行物流配送的优化，算法的设计如下：

1） 编码方法设计［6］：采用Crefenstette等提出的巡回路线编码法：假设将配送问题中所有用户所组成的列表记为W，给配送中心和每个用户分配一个1~n之间的序号，序号的排列也记为W，即W=(t0,t1,t2…tn)。配送顺序记为T，T=(t0,t1,t2,…tn)，规定每配送完一个用户，就从W中将其删除。

2） 遗传算子设计

选择算子常用的方法有轮转法、最优保存法和期望值选择方法，其中轮转法以被证明不能收敛到全局最优解，而最优保存方法可以收敛到全局最优解，故在此选用最优保存法［7］。

交叉算子一般采用单点交叉、双点交叉和均匀交叉等算子，但由于配送优化问题采用的是序号编码方法，常规的交叉算子无法直接使用，在此首先进行常规的双点交叉，然后通过路径有效顺序的修改来实现交叉运算［8］。

配送优化问题中个体编码串上的各基因与配送路径上的用户号是对应的，各基因值互不相同，可以采用倒位变异算子，通过将个体编码串中随机选取的两基因座之间的基因逆序排列，从而产生新的巡回路径［9］。

根据遗传算法的过程对实际问题进行分析、运算，在过程中加入先验知识模型，求得物流配送路径的最优解，其流程如下图1所示：

3.2.2 先验知识统计与分析

在地理信息系统的应用中，往往存在很多现实因素，若能对这些因素加以分析和处理，就可以在一定程度上提高处理的效率。在智能配送这一行业中，可以运用的GIS先验知识包括道路交通、司机的行车经验等信息。

1）道路交通信息

在目前的技术条件下，要将实时交通信息数据直接应用于智能物流配送还存在一定的困难，但是可以将已有的历史交通信息数据进行充分的利用，将其作为先验知识辅助决策。在使用历史交通信息数据之前，首先对其进行统计分析，将其按照一定的准则抽象存储于先验知识库中以备调用。

2） 司机经验

虽然根据最短路径程序算法规划的道路都是按地理距离最短优先，已经考虑了长度、车道数、道路等级等影响因素，但由于道路存在一些客观因素如修路、车流量等，可能与实际不符。物流配送老司机如果多年来都配送相同的几段道路的话，对路在线的交通状况就非常了解，根据常年累积的行车经验选择避开一些易拥堵路段，使得司机所选择的路径不一定是最短的，但是到达配送地点的时间相对较短，可以在一定程度上提高配送效率；司机在道路等级的选择上，通常选择城市道路网中等级较高的路段，除非该路段车流量大、行车缓慢，或者有更好的低级别的道路，这样司机的行车路线就能在一定程度上保证了道路等级的一致性和连贯性；除此之外司机在配送过程中，如非特别需要，对于一些生僻的、路况较差的路段选择的概率较小，而根据一般算法规划的路径为了追求里程最短而忽略了这一点。

因此将老司机的行车经验信息作为一种先验信息储存于GIS先验知识库中，在进行配送优化时综合考虑其影响，规划的结果会更切实际，实用性更强。

为了有效的运用这些先验信息，首先建立一个GIS先验知识库对其进行统一管理和调用，然后对先验知识库中的先验知识进行建模，最后指导路线的规划，先验知识建模思路如下图2所示。

4 应用实例

文中研究成果已在公司几个系统中进行了运用，实验以凯立德电子地图数据作为基础平台，以湖北省某医药公司在武汉市的药店药品配送为例，随机选取了部分门店数据和配送车辆数据进行配送规划实验（门店数为30车辆数为4），实验结果如图3所示。

3-a 为优化前系统规划配送情况

3-b 优化后系统规划配送情况

通过结果可以看出，系统成功地将配送中心的待配送任务进行了规划，利用四辆车对30家门店的送货任务进行了分配并规划了配送路线（包括返程路线）。其中图3-a是利用原有的系统对车辆鄂A-C1553进行配送规划的结果，车辆的配送里程为336.371公里，图3-b是用文中方法优化后对车辆鄂A-C1553的配送路线规划，配送里程为317.015公里，较优化前缩短里程近20公里；加入先验知识优化后车辆行走的路线为以省道优先，避开了路况较差的乡道，企业按照系统规划的路线，根据路线上客户分布顺序安排货物的装载方案，派出车辆鄂A-C1553进行配送。根据配送结果分析，该优化方案确定。提高了物流配送的效率。

5 总 结

文章将实时交通信息、行车经验等信息作为先验数据进行建模，并将其与遗传算法结合实现，应用到智能配送的优化中来，在很大程度上解决了传统算法规划的配送方案与实际不相符的问题。研究的应用表明，该研究成果对于提高物流配送的效率具有指导意义，由于条件的限制，未能将物流货物的类别对建模的影响考虑进来，这是需要进一步研究的问题。

参考文献

［1］ 叶年发,沈海燕,冯云梅.基于RFID及智能优化的物流配送方法和技术的研究［J］.交通运输系统工程与信息,2008,8(2):131-135.

［2］ 刘云霞,彭鸿广,曹玉华.不确定信息的物流配送系统实时车辆优化调度策略［J］.浙江科技学院学报,2008,20(4):289-291.

［3］ 李子豪.智慧物流平台――公路运输管理系统的设计与实现［D］.北京:北京交通大学,2011.

［4］ 张连蓬,刘国林,江涛，等.基于先验知识的GIS路径寻优算法［J］.测绘科学:2003,28(3):27-29.

［5］ 陈国良,王煦法,庄镇泉，等.遗传算法及其应用［M］.北京:人民邮电出版社,1996.

［6］ 林娜,李志.基于GIS和遗传算法的物流配送中心选址研究［J］.遥感信息:2010,5:110-114.

［7］ 王会云,肖建禄,刘登泰，等.基于遗传算法的配送路线优化［J］.后勤工程学院学报:2008,24(3):91-94.

［8］ 郎茂祥,胡思继.用混合遗传算法求解物流配送路径优化问题的研究［J］.中国管理科学:2002,10(5):51-56.

［9］ 曾国清.0-1背包问题的遗传算法求解［J］.科技信息:2006,3:242-243.省略)。