基于3G无线通信技术的物流配送车辆优化调度问题

李海涛

（四川省邮电职业技术学院，四川 成都 610067）

1 引言

经济全球化步伐的加快以及现代化信息技术的不断发展进一步促进了专业化分工的深化，伴随着这一趋势的加强，物流活动也逐渐走向信息化、系统化和专业化。从上个世纪开始，逐渐涌现出了各种专业化的物流服务，形成了现代化的物流产业链。与此同时，现代信息技术也得到了长足的发展和提升，尤其是3G无线通信技术的出现，大大提高了社会生产力和物流服务水平，3G技术在物流领域的应用尤其是在配送环节的引入，实现了配送环节的可视化管理，提高了配送作业的效率，大大降低了配送中心的作业成本。配送作业中的车辆调度问题一直以来都是该环节一个比较核心的问题，也是直接影响配送服务水平的核心环节，因此利用3G无线通信技术实现对配送车辆的优化调度，对于提高优化配送作业、进一步提高配送服务水平具有重要的现实意义。

2 基于3G无线通信技术的物流配送监控系统整体结构设计

3G无线网络通信技术是一种以互联网为核心，借助RFID无线射频识别技术、红外感应技术、GPS全球定位系统和GIS地理信息系统以及GSM数字蜂窝移动通信系统等现代化通信技术，实现互联网上的信息互联的一种信息共享和交互技术，3G无线网络技术具有传输速度快、带宽大等特点。借助3G技术，有利于实现物流活动的智能化和一体化、社会操作。

2.1 系统整体设计

根据对现代物流业务流程的分析，结合3G无线技术的特点，基于3G无线通信技术的物流配送监控系统整体结构如图1所示。其中，无线视频监控模块主要借助现场前段视频等设备对现场的作业信息进行采集，经压缩处理后利用3G网络传回至移动办公平台；在物流定位模块中，利用配置在配送车辆上的车载终端并结合GPS和GIS技术实现对车辆实时位置信息的采集，并将信息回传至移动办公平台；对于RFID射频信息读取模块，主要利用RFID阅读器采集储存于RFID标签上的商品信息并利用3G无线网络上传至移动办公平台。通过移动办公平台，可以实现对物流信息和视频信息的实时监控。

2.2 基于3G无线通信的物流配送车辆定位实现

图1 基于3G无线通信的物流配送实时监控系统总体结构图

物流配送车辆的实时调度作业中，配送车辆的实时定位是关键，物流配送中心要实时把握配送车辆的实时位置才能制定有效的调度措施。基于3G无线通信的车辆定位主要应用的技术包括3G无线通信技术、GPS技术、GIS技术等。对于物流配送车辆的实时定位，根据其功能以及对定位车辆定位处理的独立性，主要包括GPS管理及定位模块、GIS模块以及3G通信模块，通过3G通信模块能够将GPS和GIS模块所采集到的配送车辆实时位置信息传递给移动控制平台或者物流调度中心。基于3G的物流配送车辆定位功能框图及物流配送车辆定位模块总体拓扑结构如图2和图3所示。

图3 基于3G无线通信的物流配送车辆定位模块总体拓扑结构图

基于3G的物流配送车辆定位模块的主要功能包括配送车辆的定位和配送车辆的车载终端管理两部分，具体包括车辆终端设备信息资料的处理、车载终端编号、驾驶员信息、3G通信地址管理、利用卫星定位技术实现车辆实时位置信息传输等。

3 物流配送中心车辆优化调度模型构建

目前国内关于配送车辆调度问题的研究主要集中于单配送中心、多确定位置客户以及单车型非满载问题，且客户对于配送服务具有明确的时间要求，一般为软时间窗问题，即如果配送车辆未能在客户规定时间范围内送达，则客户将对配送中心采取一定的惩罚措施，基于此，本文构建带软时间窗约束的物流配送车辆优化调度模型并引入交通流量因素对车辆调度决策的影响，为了便于模型构建和求解，首先对模型作如下假设：（1）假设配送中心拥有车辆数足够多，能够满足配送高峰时的需求；（2）配送物资可混装；（3）客户需求点以及各节点装卸效率已知；（4）各客户点对配送时间要求以及单位时间惩罚费用已知；（5）配送区域路网路段长度已知；（6）路网中各个路段的最小出行速度以及自由流速度已知。

基于上述假设，可构建带软时间窗约束的物流配送车辆调度优化模型如下：

目标函数：

其中：

约束条件

模型相关参数解释如下：N表示某时段范围内需要提供配送服务的顾客数量；Nl表示某时段范围内由车辆l提供配送服务的顾客数量；Rl表示车辆l的配送路径集合，Rl={rl,k|rl,k∈{1,2,...,N},k=1,2,...,Nl}；rl,k表示车辆l服务的第k客户；cl,d表示车辆l执行配送作业的单位时间操作成本；La表示路网中路段a的长度；ra(t)表示某时刻t路段a上的车流速度；xa(t)表示某时刻t路段a上的车辆承载量；va表示路网中路段a的平均离开率；ka(t)表示某时刻t路段a上的车流密度；分别表示路网中路段a上车辆的最小出行速度和自由流出行速度；ka,jam表示路网中路段a上的阻塞密度；cd,rl,k表示如果为客户rl,k提供配送服务出现延期所产生的单位时间惩罚费用；ce,rl,k表示客户rl,k提供配送服务提前到达所产生的单位时间等待费用；trl,k表示车辆l到达客户rl,k开始服务的时间；分别表示客户rl,k要求的配送服务开始的最晚和最早时间；wrl,k表示客户rl,k需要的配送作业量；ηrl,k表示在客户rl,k处装卸作业的效率；表示车辆在客户点rl,k处的作业时间；ql表示车辆l的载重量；

上述模型中，Cf(trl,0,rl,k)为系统总成本，trl,0表示车辆l离开配送中心的时间，式（1）表示车辆l在执行配送作业时不能超载；式（2）表示车辆l执行配送作业时最大客户访问量不能超过客户总数；Nl=0表示车辆l未执行配送作业；式（3）表示所有客户都要被提供配送服务；式（4）表示每个客户均只能被一辆车提供配送服务；式（5）和式（6）为车辆闭回路约束，表示车辆执行完配送作业以后需要返回配送中心；式（7）为时间窗约束；式（8）表示车辆到达当前客户的时间=车辆到达上一客户开始服务的时间+车辆在上一客户的卸货时间+车辆从上一客户到达当前客户的运输时间+车辆在上一客户提前到达的等待时间；式（9）为路段流量约束。

4 基于自适应遗传算法的模型求解算法设计及实例分析

4.1 自适应遗传算法求解流程设计

在求解诸如上述非线性规划问题时，常用启发式算法对其进行求解。在实际应用中，传统的遗传算法步骤容易使最优解的搜索过程陷入早熟，从而使得到的最优解并非全局最优，为避免此现象，本文采用自适应遗传算法对上述问题进行求解。自适应遗传算法在进行最优解搜索过程中，其交叉率和变异率设置为随染色体适应度值变化而自适应变化，见式（10）和式（11）。

f`表示在进行染色体交叉操作时染色体适应度值的最大值，f`=max{f1,f2}；favg表示种群所有染色体的平均适应度值；f表示需要变异的染色体的适应度值；fmax表示种群所有染色体中适应度的最大值；k1,k3为交叉概率调整参数；k2,k4为变异概率调整参数，k1,k2,k3,k4∈(0,1)。

根据遗传算法基本流程以及上述对交叉概率和变异概率的调整，针对上述物流配送中心车辆优化调度模型，应用自适应遗传算法对模型进行求解的设计流程如图4所示。

图4 自适应遗传算法流程示意图

4.2 算例分析

以甘肃省兰州市某配送中心为例，该配送中心坐标为（33,77），单位为km，该配送中心服务区域范围内共有20个客户，配送中心为客户提供配送服务，每辆配送车辆的最大载货量为100箱，配送车辆在执行配送作业时每单位行驶里程配送成本为1元/km，配送车辆车速为1km/min，配送过程中车辆等待费用为0.1元/min。区域内各客户点位置以及相关信息见表1。借助GPS和GIS实时传回的车辆位置信息，利用Arcgis软件对该地区路网进行处理，可得到城关区路网各路段长度及路段节点坐标，并标出配送中心位置、客户点位置及各配送车辆实时的位置坐标。

由于本文模型考虑对配送车辆的实时调度，在实际执行配送作业时，主要根据GPS全球定位系统和GIS地理信息系统所提供的各时段实时道路交通流信息，选取某时段作为研究对象，将背景中相关参数以及该时段配送车辆运行参数输入模型并应用自适应遗传算法进行求解，求解结果见表2。

该配送方案下，配送中心总配送总成本为：Cf=12035（元）。

考虑到道路交通流信息变化较快，上述方案仅为该时段配送中心车辆调度的最佳方案，随着时间的不断推移，3G系统将不断反馈新的交通流信息，在这种情况下，配送中心应不断更新配送方案并通过GSM数字蜂窝移动通信系统和配送车辆之间的实时调度指令，实现总配送成本最低。

5 结束语

随着现代信息技术的不断发展和进步，3G无线网络通信技术也得到了快速的发展和延伸，逐渐成为通信行业的支撑技术，凭借移动性和高带宽性等优势，3G无线网络通信技术在越来越多的行业里得到了广泛的应用。作为现代物流业，大量现代通信技术的引入进一步提高了现代物流信息化、商品化和专业化的程度，本文主要从物流配送环节的车辆调度优化问题入手，借助3G无线通信网络，实现了对配送车辆的可视化管理和实时调度，并构建了带时间窗约束的配送中心配送车辆实时调度优化模型，最后应用某实例对模型进行了验证。

表1 各客户点位置坐标以及相关信息表

表2 某时段配送中心配送方案

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

[2]Bordin L.Classification in Vehicle Routing and Scheduling[J].Networks,1995,11:71-88.

[3]马卫民.第一方物流配送优化问题及其竞争策略田[D].西安:西安交通大学,2012.

[4]冯萍.退火遗传算法在运输路线规划中的应用[D].西安:西安交通大学,2011.

[5]党国英.基于GIS的物流配送车辆优化调度系统研究与实现[D].西安:西安理工大学,2009.

[6]Demenulemeester L,Laporte G,Loueaux F V.Optimal sequencing of skip collections and deliveries[J].Journal of the Operational Research Society,1997,(1):57-64.

[7]王亦鹏,王红卫.GIS在敏捷运输路径选择中的应用[J].计算机工程与应用,2012,(9):33-35.

[8]李强,黄莎白.GIS环境下的最佳路径规划[J].信息与控制,2010,29(1):45-47.

[9]陆振波,黄卫.城市公交问路系统—GIS在城市公交管理中的应用[J].公路交通科技,2011,18(5):23-25.