基于Google Maps JavaScript API的物流配送车辆调度系统设计

莫以为，何新彪

MO Yi-wei,HE Xin-biao

（广西大学 机械工程学院，南宁 530004）

0 引言

车辆调度问题(VRP--Vehicle Routing Problem)源于旅行商问题（TSP--Traveling Salesman Problem）。该问题描述：在满足一定约束条件（如货物总量不可超过车辆容量，每条路线长度不可超过车辆行驶里程，以及车辆服务节点时间必须满足给定时间范围要求等）下，组织适当的行车路线，使车辆有序地通过指定的一系列服务（取货送货）节点，并达到预定目标（如行车总路程最短、费用最小、时间最少、车辆使用量最少等）。VRP包含多条行车路径，每条路径就是一个TSP问题。

目前VRP研究大多集中在该问题的理论及算法领域，例如利用各种启发式智能算法（遗传算法、模拟退火算法、蚁群算法、禁忌搜索算法、人工免疫算法以及混合算法等）求解VRP问题[1,2]。近些年在VRP实际应用研究上，国外研究者结合各种VRP算法开发了各式各样的车辆调度软件，例如美国ESRI公司的Arelogisties系统、Roadnet科技公司的Roadnet5000系统、IBM的VSPx系统、美孚的HPCAD系统等[3]。国内车辆调度软件发展也较快，如北斗星车辆控制调度系统等，但普及化程度高的车辆优化调度软件较少。

GIS的快速发展使得根据实际地图数据完成车辆调度成为可能，将空间地理数据和物流信息数据结合并对配送决策产生作用是开发车辆调度软件的亮点[4,5]。专业GIS系统，如国外的AutoCAD、ArcGIS、MapInfo、GeoMedi和国内的Supermap、MapGIS、GeoStar、TopMap等[6]，其功能强大，但对开发能力、开发成本要求高，造成其应用门槛高。因此，第三方提供的GIS应用服务成为了非专业GIS人员应用的首选，Google Maps JavaScript API正是适应这种需求而出现的[7]。Google免费开放其地图API供用户调用，用户只需学习API使用文档即可在自己的系统上完成专业GIS系统所具有的功能，且操作调用简单，不必花费大量人力物力去维护地理信息数据。

鉴于专业GIS的高成本性，本文通过Google Maps JavaScript API提供的GIS应用服务接口获得相关空间地理信息并与物流信息紧密结合，采用模拟退火遗传混合算法（SAGA，Simulated Annealing Genetic Algorithm）设计简单可行、低成本的物流配送VRP解决方案。

1 系统架构与功能

1.1 系统结构

图1 总体架构与主要流程示意图

本文系统设计基于B/S模式方案；后台服务器语言采用C#编程，主要完成算法求解功能；服务器数据库采用SQL server 2000，用于存储客户、车辆、订单货物以及路径数据；客户端采用Ajax技术，包括JavaScript、XML、HTML/XHTML、DOM、CSS、XMLHTTP等语言，主要完成客户端与Web应用服务器、Google Maps服务器的通信交互。总体架构和主要流程如图1所示。

1.2 功能概述

图1中的步骤1-8实现向Google Maps服务器请求提取系统中所有任意两个节点（包括配送中心地点和客户地点）之间的有向最短道路距离，并将其存储到Web数据库。Google Maps服务器会提供若干条两节点之间的行驶建议路线，此处提取里程最短那条路线的距离，且因考虑了实际道路单行道不可掉头及左行车道与右行车道路径长短存在差异等情况，节点甲→乙与乙→甲的距离大小往往存在一定差异，故称为有向最短道路距离。

图1中的步骤9-15为具体求解一次车辆调度过程。在用户请求下，Web服务器根据调度任务即订单信息，获取相关节点信息及节点间路径信息，采用SAGA算法在用户指定算法参数设置条件下完成路径优化，并最终在地图上显示结果。

2 路径提取与存储

提供给SAGA算法使用的路径数据（有向最短道路距离）存储于Web数据库中。仅当配送系统有新客户加入时，才需向Google Maps服务器提取该新节点与已有节点之间的路径数据并存储到Web数据库中，其过程如图1中的步骤1-8所示。

2.1 地图加载

首先在web页面HTML源文件中利用URL地址导入Google Maps JavaScript API应用函数接口库文件，如下所示。

随后进行地图初始化参数设置，主要包括地图对象、地图路径导航服务请求对象、地图缩放比例、地图路径导航显示对象、地图中心点、地图类型、地图显示容器、街景模式、交通状况等属性的设置。

2.2 提取请求参数设置

主要完成路径导航服务请求对象google.maps.DirectionsService()、路径导航显示对象google.maps.DirectionsRenderer()、请求对象request参数的设定。request参数包括起点地址、终点地址、是否提供备用路线、是否避开高速路、是否避开收费站、出行方式等。其中起点地址和终点地址为系统中需要提取路径数据的两个不同的客户节点地址，系统定义节点甲→乙与乙→甲的路径为两个不相同路径，地址可以是能被Google Maps JavaScript API正确解析文字格式地址或经纬度格式地址。

2.3 两节点间路径数据提取与存储

客户端通过函数directionsService.route(request,function(result,status) 向Google Maps 服务器发送request参数以请求路径导航服务。若返回的status=OK，表示请求成功，否则表示无响应或响应错误，此时提取不到路径数据，则赋为有向最短道路距离无穷大。反复循环，直至所需路径数据全部提取完。最后，将提取到的路径数据及相关信息储存到Web数据库中，包括起点信息（编号、名称、地址、经纬度）、终点信息（编号、名称、地址、经纬度）、条件（是否避开高速路、是否避开收费站、出行方式）及起点到终点的有向最短道路距离。

3 配送车辆调度与基于SAGA算法的求解

3.1 配送车辆调度问题描述

本文所研究的是配送中心给若干客户配送的车辆调度问题，假设其路线是封闭的（即起点和终点同为配送中心），不考虑时间窗[8]，且车型单一（车辆容量为q，车辆净重为Q），其数量不受限。假定配送客户（节点）集，A={Ai}，i∈{0,1,...,n}，其中A0为配送中心，客户Ai货物需求量为gi（且假定gi≤q），且令配送中心货物需求量g0=0；所需最少车辆数为m；第k辆车的行车路径称为第条子路径，由所经nk个节点与配送中心组成，第k辆的nk个节点集为pk，其节点元素依次为，节点pk(l-1)与pkl间的距离为dpk(l-1)pkl；为方便起见假设其中pk0、pk(nk+1)均表示配送中心0，则配送车辆调度优化数学模型如下：

式(1)为目标函数，表示该任务运输吨公里数，其中小括弧内表示车辆从节点pk(l-1)到节点pkl时车辆的总重量（包括车辆净重和货物重量），中括弧表示到达pkl时的吨公里数；式(2)为约束条件，表示单辆车服务的所有客户需求总量不大于车辆容量；式(3)表示所有车辆服务的客户节点总数为n，且任意不同的两辆车服务的客户节点不重复；式(4)表示所需最少车辆数，中括弧表示取整。具体实现步骤如下：首先，根据式(4)确定某配送任务的出车数量m，并保持不变，把问题简化为m个路径优化问题；然后在约束条件式(2)和式(3)下通过路径的选择对目标函数1-1进行优化，确定优化调度方案。

通过分析各种路径规划的智能算法优劣性，采用SAGA进行求解。该算法因遗传算法GA的强大全局搜索能力可快速地搜索出全局较优解，同时在GA主循环中插入模拟退化算法SA，利用其良好的局部搜索能力以弥补GA的局部搜索能力较差不足，寻求全局最优解。具体地说，采用SAGA算法对m辆车的路径（包含起点配送中心）的构成长度为m+n+1的方案编码进行优化，这是为了便于交叉、变异等算子的操作，该编码方案直观，不需解码，两个数字0之间的路径即为一辆车的行驶路径。例如，m=3、n=8的路径编码047803602510表示3辆车对8个客户进行送货的路线安排，3辆车的路线分别为04780,0360,02510。由此，利用所获相关GIS地理数据与物流信息数据，采用SAGA算法搜寻优化配送方案，完成配送车辆调度。

3.2 基于SAGA的优化算法

SAGA算法中的个体表示长度为m+n+1的路径编码，且无论随机、换位法、交叉、变异产生的新个体都必须满足约束式(2)和式(3)的要求。求解步骤如下：

1）设定种群规模N，总繁殖代数X，初始代数x=0，初始温度t0，第x代温度tx，a为退火率；随机产生规模为N的初始种群P0，在P0中搜索最小值Jmin的个体Smin;

2）判断x是否超过总繁殖代数或个体Smin连续最佳保持了X0代：若是则退出，并输出Jmin、Smin；否则转到3）;

（3）重复(1)～(2)步骤L次（L为马尔科夫链长度，且L=γ*n，γ一般取100，n为自变量维数，即客户节点数）[9]；

4）在第x代种群Px中搜索目标函数值J(x)min最小的个体Sx；比较J(x)min〈Jmin，是则Jmin=J(x)min，Smin=Sx；

5）在Px中按照轮盘赌选择法产生父代1和父代2[10]，即以个体目标函数值越小被选中的概率也越大的思想选择个体；以概率pc对父代1和父代2进行交叉产生一个子代个体[11]，若交叉不成功，各以一半的概率选择其中一父代作为子代个体；以概率pm对该子代个体进行变异操作产生新个体以代替该个体[12]，若变异不成功，保持该个体作为子代个体；

6）重复步骤5）直到产生N个子代个体构成种群Px+1；x=x+1，tx=a*tx；返回步骤2）。

4 实验及结果分析

假设配送客户节点数n =20，各节点需求量如表1所示，并根据客户地址利用上述方法从Google Maps获得各节点间的有向路径距离矩阵如表2所示。

假设车辆载重量q=6吨，净重Q=2吨，根据表1数据与式1-4确定所需最少车辆数m=3；设SAGA算法参数选择为：种群大小N=100，连续最佳代数X0=300，总繁殖代数X=1000，交叉率pc=0.95，变异率pm=0.01，退火率a=0.95，初温t0=[max（dij）]*n（i,j∈n，且i≠j）；实验条件（环境下）：CUP2.6GHz、内存1.0GB、网络带宽512Kbps、Windows XP系统。

在上述实验环境下，从Google地图服务器提取到了表2中全部420条路径数据用时5分钟；用SAGA算法从46代开始找到总吨公里数最小的路径（05820671516190134111221010143171890），且该路径连续保持最小至346代，用时17秒，其总吨公里数为301.6吨公里，总路径长度为74.5km，所得3辆车路径分别如图2-图4所示。

图2 第1辆车路径

表1 各客户节点货物需求量gi（吨）

表2 各节点间路径距离dij矩阵表（km）

图3 第2辆车路径

图4 第3辆车路径

实验结果表明，在网络数据传输稳定时可方便从Google地图服务器获取数据，同时考虑到配送中心客户相对较稳定的特点，文中提出获取路径信息方法是可行的。另一方面，增加X和X0的值可搜索出更优的个体，因此通过合理设置算法参数可改善种群逐代收敛性能，在不超过总繁殖代数X内搜索出了连续最佳保持X0代的优化个体。经过实验验证，在算法参数N=20～100，X0=100～300，X=500～1000，pc=0.6～0.95，pm=0.001～0.01，a=0.75～0.95设定下[9,10]，对于客户节点数n为100以下中小规模物流配送问题，本系统能在1分钟内给出较优路径方案，完成车辆调度。

5 结论

本文车辆调度算法所用节点间路径数据源于业内公认衡量其他地图软件默认标准的Google地图[14]，其提供清晰的卫星照片地图更证明了Google地图数据的真实可靠性和准确性。本文通过Google Maps JavaScript API实现了Google Maps与实际物流配送系统结合决策生成VRP优化方案的应用系统，利用Google地图道路网数据与物流配送信息结合，通过SAGA的模拟退火算法和遗传算法的各自优势能较好地解决物流配送VRP问题。采用Google地图道路网数据取代两节点间直线距离数据，并以车辆运输总吨公里数代替运输总路径长度作为优化目标函数，更符合真实情况与实际需要。与此同时，系统的开发与维护成本低，具有较好的实用价值，还可将本方案延伸至VRP的变种问题，并结合车辆监控系统等可构成更加完善的配送管理系统。因此，本文给出的车辆调度方案对众多中小物流企业实际解决VRP具有一定的参考价值。

[1] 孙丽君,胡祥培,王征.车辆路径规划问题及其求解方法研究进展[J].系统工程,2006,24(11)：31-37.

[2] Asvin Goel,Volker Gruh.A General Vehicle Routing Problem[J].European Journal of Operational Research,191(2008)：650-660.

[3] 王厂.基于Google Map ApI的邮政运输调度系统的分析与设计[D].济南：山东大学,2010.

[4] 刘昕雨.GIS技术及路径优化算法在烟草物流配送中的应用研究[D].重庆：重庆大学,2009.

[5] 杨湘燕.基于WebGIS的物流配送路径规划系统的设计与实现[D].厦门：厦门大学,2009.

[6] 夏鼎.改进的蚁群算法解决车辆路径问题及其WebGIS实现[D].上海：上海交通大学,2009.

[7] Google Maps JavaScript API V3. http：//code.google.com/intl/zh-CN/apis/maps/documentation/javascript /basics.html.

[8] 秦本涛.基于遗传算法的车辆调度系统设计[D].浙江工业大学,2009.

[9] 王银年,葛洪伟.求解TSP问题的改进模拟退火遗传算法[J].计算机工程与应用,2010,46(5)：44-48.

[10]张建光.基于退火遗传算法的战时非满载车辆调度问题研究[D].国防科学技术大学,2009.

[11]但正刚.基于多代理的两阶段实时车辆调度系统研究[D].清华大学,2008.

[12]美国在线地图软件测评：谷歌居首必应次之.http：//tech.qq.com/a/20101006/000072.htm.