基于GIS的物流配送车辆调度实现与应用

李惠珠,宋海清

(11广东工贸职业技术学院计算机系,广东广州 510510;21中山大学岭南学院,广东广州 510000)

基于GIS的物流配送车辆调度实现与应用

李惠珠1,宋海清2

(11广东工贸职业技术学院计算机系,广东广州 510510;21中山大学岭南学院,广东广州 510000)

本文指出物流配送车辆路径 (VRP)两类模型的局限,分析在电子商务下物流配送车辆路径充分利用GIS的优势,以克服VRP数学模型求解结果的抽象性,让车辆路径优化调度简单易用,有助于物流配送企业降低物流运输成本。

物流配送;车辆路径;GIS应用

据报道,光棍节淘宝商城单日交易额9136亿。艾瑞咨询近期最新数据显示:2010年第一季度,国内B2C网上商城的销售额已经突破千亿,是2009年的2倍多。虽然中国网购用户数量已接近2亿,但电子商务的渗透率只有30%,而这个数字在美国、英国达到70%以上,可见电子商务必将带来的巨大市场和利润。电子商务的任何一笔交易,都包含着信息流、商流、资金流和物流活动。其中信息流、商流、资金流三者都可以通过信息网络完成,唯独物流,作为众流中最为特殊的一种,是实物的传递,不能通过信息网络完成,必须通过把实物位置转移到购物者中,才算完成,所以物流是完成电子商务交易过程的一个非常重要的环节,是实现电子商务的保证。电子商务公司的配送面对的不仅有批发商和零售商,还直接面对大批的最终消费者;同时电子商务不受时间、地域上的限制,较难形成集中的有规模的配送流量。这些都造成配送任务复杂而琐碎,使物流配送成本居高不下[1]。要降低配送物流成本,优化送货路线是一条降低配送物流成本的重要途径。

1 车辆优化调度

优化送货路线问题属于车辆路径问题[2](Vehicle Routing Problem,VRP)。该问题由Dantzig和Ramser于1959年首次提出,因其广泛的应用性,国内外学者对其进行广泛地理论研究与实验分析,综合运用运筹学、管理科学、经济学、组合数学、计算机科学、图论等理论知识,通过类比、演绎、推理和综合的方法,取得一定的成果。研究VRP可以合理使用调运工具,优化运输路线,降低企业物流成本。

图1 车辆路线问题的网络图形描述

研究车辆路径问题 (VRP),主要有两类模型:网络图模型和数学模型。

网络图模型 (如图1)具有直观性强,容易理解而受欢迎,但对参数的容纳能力有限。

数学模型[3]:对于VRP问题,一般以成本最小为目标,寻找满足一定约束条件的解。下面先给出VRP的一般数学模型。

首先对符号说明:

cij表示从点i到点j的运输成本,它的含义可以是距离、费用、时间等,本文中代表距离。

N:配送需求点下标集合,即 N={1,2,…,n},其中 n为配送需求点数。

点 o:为配送中心,记 N0=N∪{0}。

V:车辆下标集合,即 V={1,2,…,k},其中 k为车辆数。

Q:每辆车的装载容量(所有车辆的装载容量相同)。

di:点 i的配送需求量,我们假定

(111)为目标函数,使车辆完成配送任务的行驶总路径最短;

(112),(113)确保每个配送需求点恰好被车辆访问一次;

(114)是流守恒条件,即车辆到达某点后,必须离开该点;

(115)是车辆容量限制;

(116)限制车辆路线中不含子回路;

(117)变量约束。

数学模型 (一般包含目标函数与约束条件)具有:(i)容量大。该种模型对参数的容纳能力很大,能够表达任何大规模的问题;(ii)灵活性高。随着实际应用需求的出现,数学模型的表达形式会随着问题条件的变化而发生一些改变;(iii)通用性强。一旦将路径规划问题抽象成上述的数学模型,从模型本身就很难看出原问题所属的领域,任何可以抽象成该类型模型的其他管理决策问题都可以用这类模型表示。这一特点也使得VRP在抽象成数学模型的过程中失去了本身问题的特征。失去了车辆路径问题 (VRP)的问题特征,求解的结果要还原成用户能够理解的形式,需要寻找建模之初对这些变量所做的假定含义,这样就造成了模型使用过程的复杂[4]。

车辆路径问题(VRP)的网络图模型容纳能力的有限性,数学模型求解结果的抽象性,使车辆路径问题(VRP)在理论领域的研究较多,应用于实际较少。为了克服数学模型求解结果的抽象性,让求解结果能直接反映;同时借助计算机技术的发展(来计算最短路径)与城市路网的成熟;由 GIS来支持车辆路径问题(VRP)的研究。本文采用了GIS系统作为研究车辆路径问题(VRP)的界面,下面对GIS系统进行简单的介绍。

2 GIS概述

GIS(Geographic Information System)中文译名“地理信息系统”,是20世纪60年代发展起来的一门新兴技术。它是利用现代计算机图形和数据库技术来处理地理空间及其相关数据的计算机系统,是融地理学、测量学、几何学、计算机科学和应用对象为一体的综合性高新技术。其最大的特点就在于:它能把地球表面空间事物的地理位置及其特征有机地结合在一起,并通过计算机屏幕形象、直观地显示出来。

GIS是一类获取、处理、分析、表示并在不同系统、不同地点和不同用户之间传输空间数据的计算机应用系统,是由计算机技术与空间数据结合而产生的一种高新技术,它包含了地理信息的各种高级功能。以GIS为理论基础和软件开发平台,可以实现交通网络数据库设计、数据输入预处理、空间查询与分析、网络图形和数据之间的转换、专题地图可视化输出等功能。如果将GIS作为车辆调度系统的地理信息系统平台,就可以将车辆调度的优化算法集成到GIS平台上。这样,配送软件将可以自动制订每次的配送计划和选择最优配送路线,并且实时地显示在电子地图上,克服了车辆优化调度的数学模型求解结果的抽象性,可以提高工作效率和降低运输成本。

用户根据自己的需求,可在电子地图上设定行车路线,还可以同时设定多条行车路线,借助辅助路线决策、最短距离、最短路径、单行线和禁左等功能由导航软件来确定其最佳路径,并建立路线库,供驾驶员选择[5]。

因此,把电子地图与最短路径求解结合起来是一种降低物流配送成本的理想方法。

3 问题的描述与算法的介绍

3.1 问题的描述

在实际配送中,车辆调度为非满载的调度问题,即每个客户的货物不够一整车,每辆车承担多个点的运输任务。货车需要到指定的几个地点去卸货。优化的最终目标有两个,一个是使派车的数量最少;另一个是行驶的路程最短。据此可以将上述问题划分为配载和路径优化两个子问题。

(1)根据车辆的载重量和容积约束 (有些可能还有特殊约束,如堆码高度等)计算最少派车数量,确定每辆车经过的卸货地点。

(2)对于每辆车单独进行路径优化,使得每辆车的运行路径最短。优化的时候要根据后装先卸的原则,即最先卸载的货物要装载在最外面,方便卸货。

3.2 配送车辆行驶路线优化和配装优化

车辆行驶路线的优化问题,属于运筹学中广为研究的车辆路径问题 (VRP)。由于车辆路径问题是NP难问题,精确算法只适用于求解小规模的问题,不能满足实际需要。因此近年来研究人员都把主要精力放在启发式算法上。同样地配装问题也是NP难问题,本研究只注重载重量和容积约束,不考虑堆码问题。本系统运用聚类算法、插入算法、节约算法、扫描分组算法这些现代启发式算法来设计求解车辆行驶路线优化问题。目的是为中小型物流企业通过仿真来寻求最短配送线路及最少派车台数。

4 系统的实现

4.1 使用平台简介

笔者使用 (http:∥20211161921246/enjoyvrp/frame1htm)平台,该平台是一个辅助进行车辆路径问题研究的公共平台。该平台可完成如下几点:(1)自定义VRP问题模型;(2)整合多种高效的VRP求解算法;(3)线路规划结果对比统计;(4)GPS车辆实时监控与轨迹回放。

图2 模型设置主界面

该平台由三部分基本功能模块组成:VRP实验功能模块、GPS车辆监控功能模块以及基础数据维护功能模块。其中,VRP实验功能模块是本系统的核心,该模块包含VRP问题模型的 (需求、车辆等条件)定义、模型浏览、模型求解和求解结果评价等基本功能。界面如图2所示。

该模型主界面非常直观,电子地图把仓库及需求点清晰显示出,同时相关需求点的地理位置,需求量 (包括体积、重量及时间要求)、车辆信息及求解结果和行驶路径都能让人一目了然。

把相关的内容 (需求点位置、需求的重量和体积、车辆信息)输入,选择合适的求解算法,通过计算机计算,得出配送方案。方案包括:总体的线路规划;总路线规划的总距离;各线路的具体距离;各线路的需求点顺序及需求量 (包括货物的体积与重量);具体的行车线路;货物的重量方差及体积方差;用车的车辆信息;配送路径还可在图中直接显示。在相同的条件下,由于选用的算法不同而有不同的结果,可以进一步优化配送路径。

4.2 实现与应用

图3 界面显示了用聚类算法 (编号000170)、插入算法 (编号000169)、节约算 (编号000168)法、扫描分组算法 (编号000167)对35个规划需求点进行线路规划。左侧显示了求解结果,右侧显示了用聚类算法时各车的具体行车线路及载重。

通过选用不同的求解编号,可以显示各种算法得出的各车的具体行车线路及各线路中所有需求点需求的货物的重量和体积。

图3 显示用四种不同算法的计算结果及具体规划线路

表1显示用VRP问题的四种算法规划线路所得的距离、容积率、载重率以及其他统计指标。

表1 算例的统计指标

从表1可知,本次实例的虚拟配送路径该选择节约算法或聚类算法推荐的行车线路,它们可达到路径总距离较短,载重率高,所用车辆数量最少;聚类算法的距离方差较小,说明各线路的行驶距离相差不大,平衡了各线路的工作量,而重量方差和体积方差是四种算法中较小,对货物的装载较为均衡,有利于行车安全。扫描算法所得的距离最短,但由于多用了一台车,且无论是载重率或容积率都不是较高的,不会作为推荐的算法,相应的线路也不是所选的线路。

进一步地,基于GIS的物流配送平台还可以规划配送路径、提高容积率及载重率。笔者利用 (http:∥20211161921246/enjoyvrp/vrp/frame1htm)平台展示VRP规划的物流配送线路、实际的行车路线、配送货物的重量和体积。

图4显示了聚类算法中路线4的配送线路、实际的行车路线、需求点配送货物的重量和体积。电子地图中红色部分为线路R4的路径,左上方框内显示了线路中各个需求点配送货物的重量和体积及配送顺序。

可见,VRP规划的物流配送线路、实际的行车路线、配送货物的重量和体积都可用平台使其可视化,并且清晰具体,易于应用。

图4 聚类算法中路线4的配送线路、实际的行车路线、配送货物的重量和体积

5 结束语

电子商务的快速发展,迫切地要求物流配送快速发展作保证。中国的物流企业以中小型居多,由于信息化程度不高,效率低,成本高。这些企业要在电子商务环境下有所发展,对优化配送路径必然要重视,可以通过上述的仿真寻求最佳配送路径,基于GIS的配送车辆调度,可显示化高,求解结果克服了数学模型的抽象性,具有显示具体,清晰易用,计算速度快的特点。能够达到如下目的:

(1)利用虚拟配送方案为实际的配送寻找最佳线路,是让居高不下的物流成本下降的有效途径。

(2)直观且具体地显示配送线路、实际的行车路线、配送货物的重量和体积,可操作性强。

(3)通过模型的解中明细显示车辆装配是否均衡,有利于行车安全与货物装卸。

(4)软件易于操作,适合文化知识水平不特别高的物流人员操作,而结果直观易见且显示具体。

综上所述,随着物流信息化步伐的加快和电子商务的发展,以及全球定位系统 (GPS)的广泛应用,基于GIS的配送车辆调度系统将会有更大的发展和广阔的应用前景。

[1]李文生.基于电子商务下的物流配送研究[J].物流科技.2007(3):86-88.

[2]Dantzig G.Ramser J.The truck dispatching problem[J].Management Science,1959,10(6):80-91.

[3]戴锡.车辆路线问题的二阶段启发式算法及其在现代物流配送中的应用[D].上海:复旦大学,2004.

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

[5]刘志强,丁鹏,盛焕烨.物流配送系统设计[M].北京:清华大学出版社,2004.

The Realization and Application of Logistics Distribution VRP Based on GIS

LI Hui-zhu1,SONG Hai-qing2
(1.Department of Computer Science,Guangdong College of Industry and Commerce,Guangzhou 510510,China;2.Lingnan College,SUN Y AT-SEN University,Guangzhou 510000,China)

In this paper,the limitations of two models of logistics distribution VRP are pointed out.The technology of GIS is analyzed according to the development of electronic commerce.Full use of the advantages of GIS is proposed to solve the problem,because it can overcome the abstractness of solution results of VRP mathematical model.By using GIS,it makes VRP easy and helps logistics distribution companies to reduce transportation costs.

Logistics Distribution;Vehicle Routing Problem(VRP);the Application of GIS

U11612

A

1008-178X(2011)02-0020-05

2011-01-29

中山大学中央高校基本科研业务费专项资金资助 (大规模、多车型、分路段限行的配送路线规则问题研究)。

李惠珠 (1966-),女,广东广州人,广东工贸职业技术学院计算机系讲师,硕士,从事应用数学研究。