路况条件物流配送途径完善

时间:2022-07-05 03:47:16

路况条件物流配送途径完善

1引言

在物流运输和配送过程中,会出现由于交通事故、天气变化、上下班等因素引起车辆行驶速度的改变,进而导致配送时间的变化。此时,各点间的运输时间不能简单地将其考虑为常数,而可以将其考虑为具有某种统计规律的随机变量,服从一定的分布函数或经验概率,这就是带随机运输时间的VRP。如,经过长期的观测,人们可以知道,某条路段是否常发生拥堵或交通事故,进而对车辆经过改路段需要耗费的时间估算其概率;也可以通过配送中的数据积累或使用第三方的路况数据,得到路段的通行速度的概率相关信息。

2考虑路况条件的物流配送路径优化模型

本文选择最短总行驶距离、最小化总的服务时间、最小化违法客户时间窗的惩罚值,作为物流配送路径优化问题的三大目标。

2.1模型前提条件

对于配送车辆路径优化问题,本文建立模型的前提条件假设如下:(1)所有车辆的行驶路线的开始和结束点都在配送中心。(2)模型中假定每个客户的需求量都小于车辆装载量,且每个客户所需要货物只能由一辆车提供;在实际工作中,当客户需求量大于车辆装载量时,先将客户需求量减去除整车的装载配送量,直至客户需求量小于车辆装载量时再参与模型的优化。(3)假定所有车辆的最大装载量为某一定值,且实际装载率不超过100%。(4)模型中假定每辆车只有一条行驶路线,视车辆返回配送中心后重复发车的情况为不同车辆;在实际工作中,可以依据车辆返回配送中心后重复发车的情况,对实际所需的车辆数进行合并。(5)假定每个客户都有指定的服务时间窗口,配送须尽可能地在此时间窗口范围内到达。(6)各客户点的需求量在配送前为已知的定值。(7)配送车辆的行驶距离没有约束。(8)每个客户点的卸货时间为某一定值。(9)假定每个客户对早到或迟到的不满意程度都符合相同的线性函数关系。(10)假定路况条件服从一定的概率分布,即路段的通行时间在配送前是已知的概率信息。

2.2模型参数设置

(1)决策变量的定义:XijkYikXijk=1代表编号为k的车辆从编号为i的需求点行驶至编号为j的需求点;否则,Xijk=0。Yik=1代表i需求点由车辆k服务;否则,Yik=0。(2)各参数的定义:V代表配送中心的全部车辆的集合,即V={vk,k=1,2,…,M};R代表配送中心与客户点的集合,即R={ri,i=0,1,2,…,N},其中r0代表配送中心;qk为车辆k的最大装载量,本文假定所有的车辆最大转载量都为q0;gi为客户点i的需求量;dij为客户点i与客户点j之间的距离;tij为车辆从客户点i到客户点j之间的行驶时间;tk为车辆k从配送中心出发的时间;ti为车辆在客户点i的停留时间,包括卸货、安装及其他作业时间,本文假定所有的停留时间都是t0。Ti为车辆到达客户点i的时刻点。ai代表客户时间窗起点,bi代表客户时间窗终点,Pe代表车辆早到的惩罚系数,P1代表车辆迟到的惩罚系数。P(Ti)代表车辆在客户点i处早到或迟到的惩罚值。

2.3模型建立

(1)目标函数。本文选取车辆最小化总行驶路程、最小化总配送时间和最小化违反客户时间要求的惩罚值作为物流配送的三大主要目标,因此本文是一个多目标的VRP问题。最小化车辆总行驶路程的优化目标:minF1=NiNjMkdijXijk最小化总配送耗费时间的优化目标:minF2=NiNjMkt′ijXijk+NNtoXijk在实际的求解过程中,因本文模型中假定每辆车只有一条行驶路线,即NiNjt0Xijk=N*t0等于一个设定的常量,在优化过程中可以省去。最小化违反客户时间要求的惩罚值目标:minF3=Nj[Pemax(0,ai-Ti)+P1max(0,Ti-bi)]P(Ti)代表惩罚值,Ti表示车辆实际到达客户处的时间,ai代表客户允许的最早到达时间,bi代表客户允许的最迟到达时间,两者之间即为客户的时间窗,pe代表车辆早到的惩罚系数,p1代表车辆迟到的惩罚系数。在软时间窗条件下,允许车辆的到达时间在客户的时间窗之外,并赋以不同的惩罚程度。这种情况一般更符合实际,企业可以依据自身情况的不同,通过设置不同的惩罚系数来平衡客户满意度与成本控制两者之间的矛盾。

(2)约束条件。车辆的容量约束:NigiYik≤q0k∈V由车辆k完成的配送任务:NjXijk=Yjki,j∈R,k∈VNjXijk=Yiki,j∈R,k∈V一个客户只能由一辆车来完成配送任务:Mk=Yik=1i∈R,k∈V要求所有车辆必须从配送中心出发:X=(Xijk)∈SS={(Xijk)|i∈rj∈rXijk≤|r|-1,r∈R},k∈V该式可以消除不与配送中心连接的支路,防止出现不与配送中心相连的路径。任意客户点都在路线之中:Xijk∈{0,1}i,j∈R,k∈V任意的车辆都只有一条行驶路线:Yik∈{0,1}i,j∈R,k∈V车辆k到达客户点j的时间:Tj=NiNjt′ijXijk+NiNjt0Xijk-t0+tki,j∈R,k∈V.针对可以预测的随机性路况问题,可以将匀速状态下的配送车辆的行驶时间通过一定的计算,换算成道路状况异常时的期望的车辆行驶时间。如果车辆行驶时间服从正态分布、泊松分布等,可以计算出相应的车辆行驶时间的期望值。更实际的情况是,在配送工作中,难以知道确切的行驶时间分布,但可以根据一些因素定性地分析和估算出以不同时间通过的概率,或依据先前的运输经验获得以各种时间通过的概率(或称为频率)值,即经验分布。如以1小时通过的概率为0.8,以45分钟和1小时15分钟通过的概率分别为0.1等。即,通过将原路径可能的通过时间tij乘以一个路况条件概率系数αij,得到新的路径通过时间。t′ij=tij*αij。

3案例分析

本文采用R公司在N城市的配送中心的某日上午的配送需求样本数据,对模型求解。该日,R公司在N城市有8个客户需求点,将客户需求量进行重量化,分别需要240kg、120kg、150kg、150kg、200kg、50kg、230kg、160kg,总需求量为1300kg。虽然配送车辆的载重能力为1200kg,但由于货物形态大多是不规则的,配送车辆不可能实现满载,依据实际经验,将配送车辆的最大载重设定为580kg,经简单计算约需要3辆车来完成配送作业。各客户点与配送中心的两两间距如表1所示。3辆车的开始出发时间均为08:00,在优化模型时均处理为0时刻出发,即“车辆9:30到达某客户点1”的表示方法为“到达客户点1的时刻为90时刻”。通过收集历史数据,假定配送中心到各个需求点及需求点之间的行驶时间服从一定的概率分布,经过概率的计算,各点之间的行驶时间为表2所示。各客户点及配送中心的时间窗要求如表3.3所示。为了简化处理,各点的开始时间窗假定为初始时间,即仅结束时间窗有效。如配送中心0的结束时间窗为300,代表车辆离开配送中心送货后300分钟之内需要返回配送中心,否则将接受一定的惩罚。编写MATLAB程序,采用改进的遗传算法求解“最优”的路径,要求该路径的总长度较短,总配送时间较少,且尽量不违背客户的时间要求。在遗传算法的程序设计方面,考虑到存在8个客户点,1个配送中心,需要3辆车,MATLAB自动生成的路径的大体结构类似于:(0,1,2,3,4,5,6,7,8,0,0,0)这样的结构;此处为了减少程序计算的复杂性,可以将路径编码设定为不重复的自然数,即将上条路径结构对应为(1,2,3,4,5,6,7,8,9,10,11,12).在算子的设计方面,选择初始种群为100,遗传代数为200,交叉概率为0.2,变异概率为0.1,在Mi-crosoftWindowsXPSP3操作系统、1.73GHz的GenuineIntel(R)处理器、1G内存的计算机上求出最优解。最优解如下:目标函数值:0.001。该函数值实际为最优解的适应值大小,因为本文构建的函数适应值经过求导处理,故该结果的数值较小。最优路径:196810472113512。转化为易理解的路径结构,即为(0,8,5,7,0,3,6,1,0,2,4,0)。它的含义是:第1辆车从配送中心出发,经由客户点8,到客户点5,再到客户点7,之后返回配送中心;第2辆车出配送中心出发,经由客户点3,到客户点6,再到客户点1,之后返回配送中心;第3辆车从配送中心出发,经由客户点2,到客户点4,再返回配送中心。在本文中,由于正反向的路径长度、行驶时间相同,所以3条路径组内的行驶顺序是无差异的。此时,总路径长度:95.00;总的行驶时间为:260min;总违背客户时间窗的惩罚值为0,程序运行时间:22.438000s。可以看出,在本文的案例中,能够满足不违背客户时间要求的情况下,求解较短的路径和较少的行驶时间。值得说明的是,若不考虑总行驶时间约束和违背客户时间窗约束,可计算出的最短路径为(0,3,1,6,4,0,8,5,7,0,2,0),最短路长度为92.00,但行驶时间却增加到300,并且有违背客户时间窗的情况发生。这两个结果相比,本次优化的结果虽然略微增加了总行驶路程,却减少了总行驶时间,并且不违背客户时间窗,总体来说是较为理想的。

4总结

本文在前人研究成果的基础上,探讨了考虑路况条件服从一定概率分布的前提下,配送路径优化问题;经过本文的研究,构建相关模型,并对其进行求解,得到了预期的结果。