于GoogleMapsJavaScriptAPI的物流配送车辆调度系统设计

基于Google Maps JavaScript API的物流

配送车辆调度系统设计

Logistics delivery VRP solution based on Google Maps JavaScript API

莫以为，何新彪MO Yi-wei, HE Xin-biao

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

摘 要：针对VRP在实际应用中的需求，本文提出通过Google Maps JavaScript API提取Google

Maps道路信息，并与物流配送信息紧密结合，利用模拟退火遗传算法解决物流配送中的车辆调度问题，并将求解结果显示在Google地图上，最后通过实验验证了系统方案的可行性与可靠性。

关键词：车辆调度；Google Maps JavaScript API；模拟退火遗传算法

中图分类号：TP393.09;U116.2 　 文献标识码：A 　 文章编号：1009-0134(2011)6(上)-0022-05Doi: 10.3969/j.issn.1009-0134.2011.6(上).07

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 系统结构

本文系统设计基于B/S模式方案；后台服务器语言采用C#编程，主要完成算法求解功能；服务器数据库采用SQL server 2000，用于存储客户、

收稿日期：2011-01-17

基金项目：广西科技厅攻关项目（桂科攻0815003-3）；广西制造系统与先进制造技术重点实验室项目（桂科能0842006_

011_Z）

作者简介：莫以为（1966 -），男，广西凭祥人，副教授，博士，主要从事机电一体化及物流工程科研及教学工作。【22】 第33卷 第6期

2011-6(上)