物流配送中的车辆路径优化问题

开篇：润墨网以专业的文秘视角，为您筛选了一篇物流配送中的车辆路径优化问题范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！

[摘 要] 配送是物流活动中直接与消费者相连的重要环节。在物流的各项成本中，配送成本占了相当高的比例。运输线路是否合理直接影响配送速度、成本和效益。在高度发展的商业社会中，消费者对时间的要求越来越严格，以往的到货“日”现已转换成到货“时”，于是时间窗的概念应运而生。随着商品运输呈现小批量、多品种、多频次、及时性等趋势，多用户运输路径的确定更为复杂。因此，车辆路径问题(Vehicle Routing Problem，简称VRP)成为众多学者竞相研究的热门话题。

[关键词] 配送 车辆路径问题 时间窗 遗传算法

随着经济全球化趋势的加强，科学技术尤其是信息技术的发展突飞猛进，产品营销范围日趋扩大，社会生产、物资流通、商品交易及其管理方式正在发生着深刻的变革，与此相适应，被普遍认为企业在降低物资消耗、提高劳动生产率以外的“第三利润源”的现代物流在世界范围内广泛兴起，目前正在成为全球经济发展的一个重要热点和新的经济增长点。随着传统批发、交通运输、仓储业向现代物流转化，尤其是配送方式的采用，对运输成本和时间的有效控制日渐成为城市配送车辆路径问题的一项重要目标。VRP一直以来都是车辆调度所重点研究的方向。而在城市内采取的配送方式恰恰具备了VRP问题的一般特征和优化调度条件。

一、VRP模型的条件及假设

VRP问题是指按要求用多个车辆从配送中心对顾客进行配给货物。各顾客点的位置和需求量为己知，各车辆的装载质量己知，力求寻找一个好的配送方案，使得总代价最小(车辆尽量少，行车总距离尽量短，总费用尽量低等)，由VRP的定义不难看出，必须满足以下条件及假设：

1.仅考虑位置已知的单一配送中心，所有的配送车辆以配送中心为起点，并最终回到配送中心。

2.每条配送路径上各需求点的需求量之和不超过车辆的装载质量，被配送货物是可混装的货物。

3.每条配送路径的长度不超过车辆一次允许行驶的最大距离，配送中心有足够的资源以供配送，并且有足够的运输能力。

4.各个客户需求和所在地均已知，每个需求点的需求由且仅由一辆车一次送货满足。

5.满足总时间约束与时间窗口。必须在时间区间[ei,lj]访问点i客户，并允许在i处等待，车辆服务的总时间不能超过物流中心的时间约束。

6.多个客户之间存在优先关系，必须在访问客户j之前访问客户i。

二、带时间窗VRP模型的建立

基于文献一文中的模型，并考虑配送系统是一个服务系统，所提供的服务必须能够让客户方便、满意。配送系统的运作成本必须和配送系统其他性能参数综合进行考评，单纯对成本进行评价是没有任何实际意义的。需要关注和努力的是：要在保证配送满足客户要求、提升客户满意度的同时，通过各种技术和管理手段，降低运作成本。因此，本文将建立改进的运输路径模型，在传统的车辆配送成本最小化目标的基础上，兼顾客户对配送时间的要求，使车辆等待和延误时间之和最小化。

（1）

（2）

式中K――车队规模，即总的车辆数目；

k――车辆数目(k=1,2,……,K)；

N――有待访问的总的客户的数目；

O――配送中心；

Q――每辆车辆的容量，这里假设所有车辆同质，容量均为Q;

i,j――顾客数(i=1,2,……,N；j=1,2,……,N)；

T――个很大的数字；

C――每辆车单位运距的运费；

t0――车辆从配送中心出发的时间；

e0――车辆可离开配送中心的最早时间；

ei――到达客户i处规定最早到达时间；

l0――车辆返回配送中心的最晚时间；

li――到达客户i处规定最晚到达时间；

dij――从客户i到客户j的距离；

pj――每个客户单位卸货量的卸载费用；

mi――客户i的货运需求量；

tki、tkj――第k辆车到达客户i、j处的时间；

tij――连接客户i和客户j的行驶时间；

si――客户i处的服务时间；

wi――在客户i的等待时间，wi≥0。

两个决策变量如下：

这个模型通用性很强，经过参数的不同设定，可以转换为其它组合优化问题的数学模型。

三、带时间窗VRP模型的遗传算法求解

在模型的处理上，根据本文提出的模型单位标量不统一的特殊性来选择权重系数变化法，将变化后的多目标函数经分析和试验得出各个子目标函数的数量级大小并确定权重，最后加权化为单目标函数用遗传算法求解。

1.惩罚函数的引入。在以往的对含有时间窗约束的车辆配送系统的研究中，所研究的成本大多仅包含行驶成本，但事实上，还包括其它成本(如装卸搬运成本)，将时间窗约束转化为惩罚函数而体现在模型中。

式中c1――车辆在任务点处等待单位时间的机会成本。

c2――车辆在要求时间之后到达单位时间所处以的惩罚值(c1和c2的大小，要根据实际情况来定)。

2.建立适度度函数。根据遗传算法中适应度函数的特点，需要将原目标函数式变化为：

(4)

(5)

式中A*，B* ――变化后的目标函数值，取值范围为[0，1)；

Amax,Bmax――分别是原始目标函数。

适应度函数因此变化为：f(A,B)=α×A*+β×B*(6)

经过分析和实验发现，A*，B*经过处理后，A*的数量级一般是10-2，B＊的数量级一般是10-1。

3.用遗传算法求解带时间窗VRP模型。本文取α＝0.8,β＝0.2，用遗传算法进行求解。在运用遗传算法求解后，验证了该算法易于理解，对问题的依赖性较小，对其求解的函数要求简单，实现起来简单高效，若参数选择的合理，收敛速度很快，但是遗传参数的控制对于算法的收敛速度影响很大，在参数选择方面有一定难度。虽然文中使用的是根据以往学者经验选定的参数，但计算表明最优解所在“代”数的稳定性不是很好，这也是以后需要进一步研究的地方。

四、结论

在传统的车辆配送成本最小化为目标的基础上，兼顾客户对配送时间的要求，建立了带时间窗的车辆路径优化多目标模型。在对模型的处理上，将两个量纲不统一的子目标函数除以各子目标函数的最大值后使其变成无量纲的函数，并通过权重系数变化法将各个子目标函数线性加权和作为多目标优化问题的适应度函数，使得多目标优化问题转化为单目标优化问题后再用遗传算法求解。

参考文献:

[1]王 惠:引入顾客满意度求解车辆优化调度问题.大连海事大学硕士论文,2006:1～13

[2]盛丽俊:带有时间窗的车辆路径问题的优化研究.大连海事大学硕士论文,2002:13～57

[3]牟燕妮:物流配送中路径优化的选择研究.沈阳工业大学硕士论文,2006:28～41

[4]周 明 孙树栋:遗传算法原理及应用.国防工业出版社,1999:130～137

[5]张先君:不确定运输问题的模型与算法.重庆大学硕士论文,2006:1～8