基于云计算的冷链物流配送车辆路径优化方法研究

刘 镇，徐优香，王 译

（江苏科技大学 计算机科学与工程学院，江苏 镇江 212003）

物流配送信息化是物流发展的趋势，冷链物流配送信息化过程中存在的问题有：运输车辆实时路况信息的获取，物流车辆的配送路线的快速计算，运输车辆动态信息的实时获取等，这些都是在提高配送效率方面亟待解决的问题。虽然目前国内对物流车辆路径问题的研究已有一定的成果[2]，但是研究还处于初级阶段，仍处在进一步研究和探讨的问题，主要有以下几个方面：

1）研究的问题大部分是对确定性问题的研究，即冷链物流中心、冷藏产品需求量、车辆的位置都是确定的，对复杂情况下路径问题的研究比较少。

2）对于实际冷链物流配送中的多种不确定性[1-2]因素，在现有的研究中主要集中在针对单一因素引起的动态车辆路径问题的研究，对实际冷藏车的位置、交通路况、天气等因素较少综合考虑。

3）冷链物流动态车辆路径问题对实时性的要求较高，需要在有效的时间范围内处理各种变化的信息，并提供计算结果，则处理该类问题的并行算法需要进一步分析和研究。

4）现有的配送车辆路径问题的研究中，针对冷链物流这种特殊物流车辆路径问题的研究比较少。

本文利用云中心中多源海量信息，采用云处理方法研究冷链物流配送实时车辆路径优化问题。

1 冷链物流配送车辆路径优化问题探讨

1.1 冷链物流的特点

与常温物流相比，冷链物流具有以下特点[3]：

1）产品具有易腐性，冷链物流配送的货物为生鲜产品、速冻食品、药品等，配送过程中由于各种原因会使产品质量逐渐下降。

2）产品具有时效性，由于冷场产品具有易腐蚀性，且生命周期比较短，其生产、贮存、配送和销售要在短时间内完成。

3）对运输装备具有特殊要求，由于一天中气温会随着时间推移而放生变化，因此在不同的气温下为了维持产品在适宜的低温环境下，配送的车辆必须为冷藏车。

鉴于以上特点研究冷链物流配送车辆路径优化的问题，其目的是快速的为冷藏车提供实时最优路径，降低配送成本，提高配送效率。

1.2 云计算环境下冷链物流配送车辆路径优化的优势

基于云计算的冷链物流配送车辆路径优化问题的数学模型本质上与传统冷链物流配送车辆路径优化问题的数学模型是一样的，均为通过合理安排车辆的配送路线和行车时间，使目标函数最优，即配送时间最短和成本最低，区别在于模型前提条件的构建，传统优化模型中所有的因素（货物需求量、客户位置、冷藏车载重量等）都是确定的，而基于云计算的冷链物流的车辆路径优化模型中有些因素（车辆的实时位置、行驶车速、车厢环境等）是动态变化的，该模型能有效的降低冷链物流配送成本和时间，提高服务效率，更具有实用价值，基于云计算[4]的冷链物流配送车辆路径优化服务具有以下优势。

1）云计算将各种分散独立的应用资源集中在同一个平台下。云中心中有丰富的海量信息资源，如构建冷藏车优化模型所需的实时交通信息、天气信息、物流信息等，用户通过统一接口获取所需多源数据资源，实现所需物流配送业务的自适应。

2）云模式中将所有计算、应用资源集中起来，通过软件自动管理，在云端以服务形式向用户提供基础架构、应用服务、软硬件资源等，冷链物流企业通过SaaS（软件即服务）模式取得所需服务，不需要购买昂贵的硬件设备，也无需负担频繁的升级维护费用，只需支付低廉的服务费用即可所需的服务，提高物流的配送服务效率。

3）云计算实现资源开放和统一访问，在云计算上构建冷链物流车辆路径优化应用服务，则用户通过统一的接口就可以获得物流配送的信息资源，构建自己的应用。

1.3 云计算中冷链物流配送的应用模式

云数据中心有交通信息、天气信息、路段信息、地理信息等多源的海量信息，利用这些信息建立于云计算的冷链物流配送车辆路径优化服务平台（其架构图如图1所示）。

图1中底层资源层包括各种服务器、网络等硬件设备，以及各种分散的冷链物流系统外的应用资源如交通、天气等系统，通过虚拟化技术将存储虚拟化、网络虚拟化和服务虚拟化，形成庞大的资源池，其中在构建冷链物流配送车辆路径优化的服务平台的应用中，将分散的冷链物流系统外的应用资源通过虚拟化技术将数据集成形成车辆优化服务的中间件，并提供统一的访问接口，从而为上层的服务平台的构建提供资源支撑。

图1中冷链物流配送车辆路径优化的服务平台通过优化模型的求解实现冷链物流配送车辆的动态路径优化，该平台向下连接资源层，动态的聚合所有资源，向上通过接口为用户提供可靠的最优路径。

图1中上层服务应用层通过提供的服务的接口，用户可以通过网络随时、随地接入应用服务层，访问需求的冷链物流配送车辆的动态路径优化服务，接入服务平台的方式可以为Web服务接口、浏览器、桌面应用程序及移动终端等。

图1 基于云计算的冷链物流配送车辆路径优化架构图Fig.1 Cloud-based cold chain logistics distribution vehicle routing optimization architecture diagram

基于云计算的冷链物流配送车辆路径优化服务平台，能够有效的解决冷链物流配送车辆实时路径优化中对实时信息的需求。平台中通过统一访问接口获取云数据中心中所需的多源数据信息资源，分析冷链物流配送的综合成本和配送时间，构建冷链物流车辆出行的路径优化模型，并利用云中心的计算资源，在有效的时间内快速的计算出有效的实时优化路径，提高物流服务效率，使冷链物流的配送成本达到精细化的管理。

2 基于云计算的配送车辆路径优化模型

2.1 冷链物流车辆配送路径问题描述

根据图1构建冷链物流配送车辆路径优化的架构，其优化模型的最终目标为车辆行驶总时间和配送成本最优，但是当获取的信息源变化时，其优化模型会有差异。在此以获取云中心的实时交通信息为例，建立冷链物流配送车辆实时路径优化模型，需满足的约束条件如下：

1）实时提取冷藏车所在位置的路段的车速和道路信息；

2）每个客户的总需求量不超过车辆的最大装载量；

3）每条配送运输路径的总长度不能超过车辆一次配送的最大行驶距离；

4）货物在一定的时间范围内到达，若超过时间范围，则支付一定的罚金；

5）配送过程中车厢内环境温湿度要在一定的范围内，否则将影响客户对产品的满意度；

6）道路宽度大于车辆的宽度。

数学描述：冷藏车从物流中心的仓库出发，车辆一次配送的最大行程为S，冷藏车的最大装载量为Q，车辆的宽度为L，为N个客户供货，已知每个客户点i的位置及货物的需求量qi，客户i到j的运输时间为tij，集合Rk表示第k条路径，其中集合元素rki为客户rki在路径k中的顺序为i，设rk0表示车辆出发的配送中心，车辆在第k条路径上的实时速度为Vk，云计算中心获取的实时路网信息Lk，以车辆配送时间和成本为目标函数。

2.2 冷链物流配送车辆路径优化模型

对冷藏车辆路径优化模型的分析包括配送时间和配送成本的分析，在架构中通过统一的接口访问交通信息云，获取车辆所在位置的交通信息进行配送时间分析，配送综合成本分析包括固定成本、运输成本、货损成本、能源成本和惩罚成本的分析。

2.2.1 配送时间分析

通过在云中心的实时交通信息中获取车辆行驶中所在路段的实时交通信息，进行配送时间的计算。车辆所在位置路段平均车速Vi、车道宽度LRi及允许通行车辆的吨位。根据Vi的大小判断路段的交通拥堵程度和预测车辆经过所需的时间tj（j-1）。当Vi=0时，表示该路段当前处于拥挤状态，只有当车道宽度LRi大于车辆宽度L并且允许通行车辆的吨位QRi大于车辆的总吨位Q时，路径i才有被选择的可能，因此车辆完成配送的总行驶时间T如公式（1）所示。

2.2.2 配送综合成本的分析

1）固定成本

运输车辆的固定成本C1有驾驶员和押运员的工资和车辆损耗的成本，C1=f为常数。

2）运输成本

车辆的运输成本C2包括车辆的油耗、维修和保养成本，与车辆行驶的里程数呈正比，如公式（2）所示。

cij为冷藏车在路段（vi，vj）上的运输成本，并且cij=cji，其中xij用0，1表示，xij=1表示冷藏车经过了路段（vi，vj），否则xij=0。

3）冷藏品损坏成本

冷藏品的损坏成本包括3种情况：第一，由于运输时间和卸货时间的长短造成的货损；第二，服务顾客时，车厢门的频繁开启造成车厢内的冷空气与外界空气交替流动，导致车厢内温度上升，使冷藏品遭到损坏；第三，由于路况的好坏程度，使冷藏品遭到损坏。冷藏品损坏成本用C3表示，如公式（3）所示。

其中，r表示产品的单价，λj为0，1变量，λj=1表示该冷藏车服务客户j，否则λj=0；α1为产品运送过程中损坏的比例；tij表示客户i到客户j所用的时间；α2表示产品在车厢门开启及装卸过程中损坏的比例；βj为客户j的货物的数量；α3表示车辆运输过程中造成产品损坏的比例；sij表示客户i到客户j之间的里程数。

4）冷藏车辆的能源成本

冷藏车的能源成本主要是消耗制冷剂的成本。制冷剂消耗量跟车厢的传热系数、车厢内的温度、车体内外的表面积及外界的温度有关。制冷剂消耗量的计算公式，如公式（4）所示。

其中G表示制冷剂的消耗量，a为常数；b为传热系数；S为车体内外的平均表面积，Δt为车厢内外的温度差。则车辆行驶中的制冷成本用C4表示，如公式（5）所示。

其中r1为制冷剂的价格，tij为从客户i到客户j的时间，xij为0，1变量。

打开车门时外界空气直接与冷藏车内的空气对流，发生冷热交替，因此计算打开车厢门的制冷成本只需计算由车门的热交换而消耗制冷剂的成本，用C5表示，如公式（6）所示。

其中ti为车辆在客户i停留和等待的时间，S为车门的面积。

5）超出客户配送时间的惩罚成本

向客户配送货物有时间限制，在此采用软时间窗的限制方法进行处理，即对客户需求的货物在一定的时间范围内到达，若未能按时到达，则将对物流配送企业给予一定的罚金。则因不在时间窗内将产品送到客户点而产生的处罚成本用C6表示，如公式（7）所示。

其中ω1、ω2分别表示冷藏车辆早于和晚于时间窗将货物卸下而带来的损失成本。sj为车辆到达客户j的时刻，tj为车辆在客户j处等待的时间。

6）其他成本

冷藏品配送过程中，在有时间限制条件下，会产生其他费用如：在高速路上行驶产生高速的收费成本等。用C7表示，如公式（8）所示。

其中，式（9）将时间和成本作为优化的目标函数，模型求解时根据其在实际冷链物流中的重要性赋予一定的权重W1和W2。式（10）为冷藏车配送总时间，等于车辆的行驶时间和其在客户处的总停留时间之和。式（11）为冷藏车配送成本等于固定成本、运输成本、损坏成本、能耗成本、惩罚成本之和。式（12）保证运输路径上各客户的货物需求量之和小于车辆的最大装载量。式（13）保证车辆每次配送行驶的最大距离小于车辆的最大行驶距离。式（14）为车辆到达下一个客户点的时刻＝车辆到达当前客户时刻+在当前客户等待卸货时间+在当前客户卸货时间+从当前客户到达下一客户的行驶时间。式（15）表示车辆在客户处等待时间由服务时间窗开始时刻和车辆到达客户的时刻决定，到达时刻早于服务时间窗开始时刻，则车辆在客户处等待，到达时刻晚于服务时间窗，则等待时间为0。式（16）保证每个客户都被运输车辆服务到。式（17）保证每个客户由一辆冷藏车服务。式（18）保证行驶路段路宽大于车辆的宽度。

3 路径优化模型求解

并行计算是云计算应用具体实现的关键技术，因此，本文在云计算环境下，利用云中心的计算资源，采用粗粒度并行遗传算法[5－10]对冷藏车路径实时优化模型进行求解，可以加快优化路径的计算效率。其流程图如图2所示，随机生成m*n个子群体分布在可行集内，依处理器个数将群体分割成m个子群体，每个子群体有n个个体，每个子群体在不同的处理器上独立的并发执行遗传操作，每个子群体最后都会找到一个或多个局部极值点，通过子群体之间的信息传递，使采样点集中在最优解的区域，经过t次操作后搜索出最优个体。其实现步骤如下：

图2 并行化遗传算法流程图Fig.2 Parallel genetic algorithm flowchart

步骤1：种群初始化：通过随机方法产生m*n个体，每个个体对应一个解，形成初始种群；

步骤2：将初始种群平均分为m个子种群；步骤3：主循环开始While i≠t do

步骤3.1：while k≠n do

步骤3.1.1：染色体编码：根据冷链物流车辆路径特点，对产生的种群进行二进制编码；

步骤3.1.2：计算函数的适应度值：算法使用适应值来评估个体所对应行车路径的优劣，个体适应度越大则被遗传到下一代的概率越大，本文中适应值函数取目标函数的倒数；

步骤3.1.3：选择：从种群中选择适应环境的个体，适应值越高的个体被选择的几率就越大；本文采用轮转法作为选择方法，选择概率为为种群个数；

步骤3.1.4：交叉：对两个不同个体的相同位置的基因进行交换，产生新的个体，采用OX方法进行交叉；

步骤3.1.5：变异：以相同的变异率改变染色体的一个或几个基因，每条染色体的变异几率相同；

步骤3.1.6：生成下一代个体；

步骤3.2：选取适应度值较好的个体；

步骤4：获取最优个体；

步骤5：输出结果。

4 实验仿真

根据利用实时交通信息建立的模型在云计算冷链物流配送车辆路径优化服务平台中的处理过程如图3所示。

图3 模型仿真工作原理图Fig.3 Schematic diagram of the model simulation work

为了验证云计算环境下求解的有效性，本文以镇江恒伟物流公司的冷藏车向客户运送冷藏土豆条为例。配送中心编号为”0”，客户i的需求量qi，卸货时间si，客户之间位置如表1及要求服务时间范围如表2所示。配送车辆在最大载重量为4.5t，车辆从配送中心出发，假设车辆固定成本f＝1 000，单位运输成本c0＝4，车内温度为－10℃，车外温度为30℃，车辆使用液态氮为制冷剂，每千克液氮价格假设为4.5元，则a＝0.91，b＝4.5，S＝16，K＝1，Δt＝50，惩罚成本为5元/分钟，设冷藏车要向8个客户配送土豆条。设定种群大小N为30，交叉概率Pc为0.7，变异概率Pm为0.05，最大迭代次数T为500。

表1 各客户点的距离Tab.1 Distance of each customer

表2 客户时间窗范围及需求量Tab.2 Scope of the customer time windows and the demand of goods

根据配送中心对车辆配送成本和配送时间的关注程度不同设置不同的比重，模拟云中心实时路况信息，实验环境为同一个局域网内4台PC机组成。情况1：令W1＝0，W2＝1，得到最优路径：0－6－7－3－1－4－2－8－5，总成本为1 620元，总里程数为72 km，车辆行驶时间为2.17小时，计算时间为10.79 s；情况2：令W1＝1，W2＝0，得到的最优路径：0－5－6－7－2－4－3－1－8，车辆行驶时间为1.84小时，总成本为1 736元，总里程数为76 km，计算时间为11.56 s。计算结果均在有效的时间范围内得出最优路径，同时，根据对对车辆配送成本和配送时间的关注程度不同，所计算结果的时间和花费也不一样，同时，在W1＝0，W2＝1时采用不同个数的处理机，算法执行的时间也不一样，在一定程度上处理器个数越多，其计算时间越短。如表3所示。

表3 不同个数处理器执行时间比较Tab.3 Comparison of different processors execution time

5 结束语

文中介绍了冷链物流相对常温物流的特殊性，分析了采用云计算进行冷藏车辆实时路径优化的意义。利用云计算技术通过统一的接口获取实时路径优化所需的实时多源信息，建立了冷链物流配送车辆路径优化的应用服务架构。本文并在该架构下，获取实时交通信息，分析冷藏车辆的行驶速度和路况，计算配送的总时间，同时对冷藏配送的固定成本、运输成本、能源成本、货损成本、惩罚成本等进行分析，以配送的总时间和成本为依据建立了冷链物流配送车辆路径优化模型；根据并行计算是实现云计算应用的关键技术，本文利用利用粗粒度并行遗传算法对模型进行求解，仿真结果验证了基于云计算冷链物流车辆路径优化方法的有效性，提高了配送服务效率。

[1]刘云霞，彭鸿广，曹玉华，等.不确定信息的物流配送实时车辆优化调度策略[J].浙江科技学院学报，2008，20（4）：289－291，320.LIU Yun-xia，PENG Hong-gang，CAO Yu-hua.Strategy of vehicle optimal scheduling about logistics delivery based on indeterminate information,Journal of Zhejiang University of Science and Technology，2008，20（4）：289－291，320.

[2]白世贞，丁旭.动态行程时间车辆路径规划问题研究[C].//第十三届中国管理科学学术年会论文集，2011：53－58.

[3]苏云，刘泽勤.冷链物流配送现状及其能耗分析[C].//第五届中国冷冻冷藏新技术新设备研讨会论文集，2011：22－25.

[4]陈全，邓倩妮.云计算及其关键技术[J].计算机应用，2009，29（9）：2562－2567.CHEN Quan，DENG Qian-ni.Cloud computing and its key techniques[J].Journal of Computer Applications，2009，29（9）：2562－2567.

[5]武金瑛.一种粗粒度并行遗传算法及其应用[J].计算力学报，2002，19（2）：148－153.WU Jin-ying.A parallel genetic design method with coarse grain[J].Chinese Journal of Computational Mechanics，2002，19（2）：148－153.

[6]易荣贵，罗大庸.基于遗传算法的物流配送路径优化问题研究[J].计算机技术与发展，2008，18（6）：13－15，19.YI Rong-gui，LUO Da-yong.Study of the optimizing of physical distribution routing problem based on genetic algorithm [J].China Journal of Highway and Transport，2008，18（6）：13－15，19.

[7]Ana Osvald a，Lidija Zadnik Stirn b.A vehicle routing algorithm for the distribution of fresh vegetables and similar perishable food.Received 26 March 2006;received in revised form 19 July 2007;accepted 20 July 2007;Available online 2 August，2007.

[8]Ying,Wang,Xi,Chen.Research on Vehicle Routing Problem of Cold Chain Logistics[C].//2010 International Conference on Multimedia Information Networking and Security.2010：329－334.

[9]王祥生，马寿峰.实时路况信息下配送路径的优化[J].工业工程，2008，11（1）：113－116，125.WAG Xiang-sheng，MA Shou-feng.Optimization of delivery routes based upon real-time traffic information[J].Industrial Engineering Journal，2008，11（1）：113－116，125.

[10]唐健，史文中，孟令奎，等.基于遗传算法的时相关动态车辆路径规划模型[J].武汉大学学报：信息科学版，2008，33（8）：875－879.TANG Jian，SHI Wen-zhong，MENG Ling-kui. Timedependent dynamic vehicle routing based on genetic algorithm[J].Geomatics and Information Science of Wunan University，2008，33（8）：875－879.