Management Science and Engineering
Vol.07 No.02(2018), Article ID:25575,7 pages
10.12677/MSE.2018.72015

Research on the Problem of Taking Delivery Vehicle Routes for Multiple Vehicles with Time Windows at the Same Time

Jing Xu

School of Economics and Management, Beijing Jiaotong University, Beijing

Received: Jun. 1st, 2018; accepted: Jun. 19th, 2018; published: Jun. 26th, 2018

ABSTRACT

This paper mainly studies the problem of vehicle path planning in Guangzhou Panyu Distribution Center. Firstly, aiming at the delivery before picking mode in the previous vehicle operation which generates the circuitous route of the vehicle, the no-load of the vehicle during the return journey, the irrational route planning, and the problem of long delivery time, we adopt an integrated point of view while considering both the customer who has the picking requirements and the customer who has the delivery requirements. All the delivery orders and picking orders are brought together to the distribution center on the previous day, so that each customer’s picking demand and delivery demand are confirmed based on the order information of the previous day; thus, the location and demand of the distribution center and each customer can be determined so as to obtain and delivery at the same time. The delivery is for the goods received at the distribution center on the day, and the pickup is for the customer who needs to deliver the goods the day before. Based on the basic VRPSDP model, two factors, multi-model and time window, were added to optimize the total cost of the distribution vehicle, and the simultaneous acquisition and delivery operation mode of the T Company in Guangzhou Panyu Distribution Center was given.

Keywords:Vehicle Path, Process Optimization, Multiple Models, Time Window, VRPSDP, Genetic Algorithm

带时间窗的多车型同时取送货车辆路径 问题研究

徐静

北京交通大学,经济管理学院,北京

收稿日期:2018年6月1日;录用日期:2018年6月19日;发布日期:2018年6月26日

摘 要

本文主要研究广州番禺配送中心的车辆路径规划问题,首先针对之前车辆运行中的先送货后取货模式,产生车辆运行路线的迂回,以及车辆在回程中的空载,路径规划不合理,送货时间长的问题,采用集成的观点同时考虑有取货要求的客户和有送货要求的客户,把所有的送货订单和取货订单在前一天汇集到配送中心,这样每个客户的取货需求量和送货需求量根据前一天订单信息得到确认;从而可以确定配送中心以及每个顾客的位置和需求量,从而进行同时取送货,送货是针对当天的配送中心收到的货物,取货是针对前一天有发货需求的客户。在基本VRPSDP模型的基础上,加入多车型和时间窗两个因素,以配送车辆总的成本为优化目标,给出T公司广州番禺配送中心同时取送货的运作模式。

关键词 :车辆路径,流程优化,多车型,时间窗,同时取送货,遗传算法

Copyright © 2018 by author and Hans Publishers Inc.

This work is licensed under the Creative Commons Attribution International License (CC BY).

http://creativecommons.org/licenses/by/4.0/

1. 引言

车辆路径问题最早是由Dantzig和Ramser [1] 于1959年首次提出的,并设计了基于线性规划的求解过程。目前对带时间窗同时取送货车辆路径问题的研究主要有两个方面:第一个方面是对同时取送货车辆路径模型的研究;第二个方面是对模型算法的研究。关于同时取送货车辆路径模型的研究,许多学者都对单车场确定需求的同时取送货问题进行研究过。Dethloff [2] 首次建立了VRPSDP问题的数学模型,并设计了依据行驶距离、车辆剩余载重能力、综合剩余载重能力以及径向距离惩罚四类插入原则的构造式启发算法,通过保留较多的车辆剩余承载空间,增大车辆访问剩余客户的自由。陈静 [3] 以运输成本为目标建立了确定需求的单车场同时取送货车辆路径模型,把人工费用、燃料消耗、轮胎损耗、保修费用和折旧五项成本综合考虑作为运输成本,并采用遗传算法对模型进行求解。

在求解带时间窗的同时取送货的车辆路径问题时,遗传算法和改进的遗传算法得到了国内外许多学者的广泛关注和使用。葛显龙,许茂增,王伟鑫等 [4] 针对城市多区域协同发展造成的商业中心相对分散的现状,提出“多对多”的城市网络化联合配送机制。A. Serdar Tasan和Mitsuo Gen [5] 对具有同时取货和交货的车辆路线问题,提出了一个基于遗传算法的方法来解决这个问题。为了说明所提出的方法,用参数设置来给出计算示例。

对VRPSPD问题研究均假设顾客点进行同时送货和取货服务的车辆是同质的,即车辆具有相同的装载能力、相同的固定费用、相同的最大行驶距离约束等,并且通常假设车辆数无限 [6] [7] 。但是在现实生活中,物流公司所拥有的车辆一般由一组异型的车辆组成,这些车辆具有不同装载能力、不同的单位旅行费用,使用车辆具有不同的固定成本,而且由于受资金约束,物流企业拥有的各种类型车辆数目也是有限的,同时,为了降低人力成本、车辆固定成本、车辆行驶成本、时间成本,物流公司更趋向于在确定客户服务需求的情况下同时进行送货和取货。本文作者研究车辆路径问题,即具有多车型同时取送货的车辆路径问题,采用遗传算法进行求解。

2. 问题描述与模型建立

2.1. 问题描述

根据番禺配送中心的实际作业情况,本文将传统的同时取送货的车辆路径问题进行重新定义:给定一个配送中心和多辆配送车辆,多量车辆从番禺配送中心出发,分别根据安排好的路线到各个客户处送货,同时将具有取货需求的客户的货物运回配送中心。这里配送中心送的货物是当天需要配送的货物,而运回的货物则是客户前一天需要运回的货物。要求在给定的约束条件下,合理安排车辆的行走路径,在综合考虑各车型的固定成本和可变配送成本的前提下,以总成本最小为目标,以尽可能提高车辆满载率、减少出行次数为思路,构建多车型的同时取送货的车辆路径优化模型。本文研究的车辆路径问题的假设如下:

1) 只有1个配送中心,且配送中心的地理位置已知;

2) 货物可以混装;

3) 配送中心与需求点的坐标位置及送货量和取货量均已知;

4) 各种车型的车辆数已知,且各车型的固定费用、旅行费用、车容量均已知;

5) 每辆车服务1条回路,由番禺配送中心出发最终回到番禺配送中心;

6) 每辆车在行驶中的车载质量不超过该车型的容量限制;

7) 每辆车每次的配送距离不超过该车型允许的最大行驶距离;

8) 每个需求点能且只能由同一辆车进行服务,每个客户最多被服务两次;

9) 货物在运输途中不会变质损坏;不考虑司机的工作时间;不考虑道路的通行情况;不考虑运输时的规章制度等。

2.2. 模型构建

模型参数说明:

n:客户数量,

C:客户节点集合, C = { 1 , 2 , 3 , , n }

A:所有客户点和配送中心的集合,其中 A = C { 0 } ,其中D为配送中心。

φ = { 1 , 2 , 3 , , K } 为车辆类型集合,共K种;

mk:不同类型的车辆数,总的车辆数为 M = k = 1 K m k

ϕ k = { 1 , 2 , , m k } :k为类型车辆的车辆集合;

Qk:车辆的最大负载能力;

z k l :第k种车型第l辆车的派车费用;

Lk:车辆的最大行驶距离;

Dij:客户i和客户j之间的处的距离;其中 i A , j A

si:客户i处的送需求量;

qi:客户i处的收需求量;

Uikl:k类型车中的第l辆离开顾客i时的载重量( 0 U i k l Q k );

[ai, bi]:客户i的时间窗;

tij:客户i到客户j之间的行驶时间;

ti:客户i的服务时间;

sikl:第k类型的第l辆车到达客户i的时间;

d:等待惩罚系数,如果车辆到达i的时间早于ai

e:迟到惩罚系数,如果车辆到达i的时间晚于bi

Wijkl:k类型车辆中的第辆l从客户i到客户j时车上的载重量。

令决策变量xijkl定义如下,其中 i j A

x i j k l = { 1 , k l i j 0 ,

y i j k l = { 1 , i k l 0 ,

基于以上符号和决策变量,建立如下模型:

min Z = { i = 0 I j = 0 I k = 1 K l = 1 m k D i j x i j k v k + i = 0 I i = 0 I k = 1 K l = 1 m k f x x 0 i k l + d j = 1 I max ( a j s j l , 0 ) + e j = 1 I max ( s j l b j , 0 ) } (4.1)

Subject to:

i = 0 I X i p k l = j = 0 I X p j k l (4.2)

k = 1 K i = 0 I l = 1 m k X i j k l = 1 (4.3)

i = 1 I k = 1 K l = 1 m k X i p k l = j = 1 I k = 1 K l = 1 m k X p j k l (4.4)

i = 0 I k = 1 K l = 1 m k X i 0 k l = j = 0 I k = 1 K l = 1 m k X 0 j k l = M (4.5)

i = 1 I s j y i k l Q k (4.6)

i = 1 I q j y i k l Q k (4.7)

0 = u i k l j = 1 I x i j k l ( s i q i ) Q k (4.8)

i = 0 I j = 0 I x i j k l d i j L k (4.9)

x i j k l ( s i k l + t i + t i j s j k l ) 0 (4.10)

a i ε s i k l b i ε (4.11)

0 W i j k l Q k (4.12)

x i j k l = 0 1 , y i k l 0 (4.13)

其中,式(4.1)为目标函数,表示最小化总的行驶成本,第一部分表示车辆的运输费用,从客户i到客户j的运输费用一般与车辆行驶距离成正比;第二部分为运输车辆的固定成本之和,xoikl表示第k类型的第l辆车是否从配送中心驶向客户i;第三部分表示车辆取送货时不满足客户时间要求时的惩罚成本;式(4.2)是车流量守恒式,表示客户点i流出的车辆与客户点j流入的车辆是同一车型的同一辆车;式(4.3)表示每个顾客都必须被某种车型的车服务1次,且仅被服务1次;式(4.4)为车辆流约束,表示一辆车到达一个客户点完成服务后必须离开这个客户点;式(4.5)表示每辆车完成任务后,必须回到车场;式(4.6)表示限制每辆车所有送货量不得超过车容量;式(4.7)表示每辆货车所有取货量不得超过车容量;式(4.8)表示车辆在行驶过程中,任一顾客点的载货量都不能超过车容量;式(4.9)表示每条配送路径的长度不超过车辆1次配送的最大行驶距离;式(4.10)表示第K类型的车辆l从客户i向客户j行驶的过程中,在时间之前不能对客户j进行服务;式(4.11)为时间窗约束条件;式(4.12)确保每辆车的载货量不能超过车辆的最大负载能力;式(4.13)为决策变量的属性。

客户点的时间窗约束分为硬时间窗约束和软时间窗约束两种,前者要求车辆必须在时间窗内到达,若车辆到达客户i的时间早于ai,则配送车辆需要在i处等待,而到达时间不能晚于bi,即约束(4.11)中ε = 0,且目标函数(4.1)中的d = ∞,e = ∞;后者不要求配送车辆一定要在时间窗内到达,但是若其到达客户i的时间早于ai或晚于bi,需要支付一定的惩罚费用,即约束(4.11)中ε = 0。

3. 算例分析

现有12个需求客户,客户D表示配送中心,i表示客户编号,xi表示客户的横坐标,yi表示客户的纵坐标,si表示客户的送货量,qi表示客户的取货量(单位:吨),服务时间窗范围[ai, bi],配送中心及各客户之间的距离由表1给出,配送中心以及客户点信息由表2给出。通过表1表2给出的配送中心以及各个客户点的信息,根据模型利用matlab工具,采用遗传算法进行迭代,迭代次数为400次,如图1所示,在迭代进行到50次以后,结果趋于稳定。利用遗传算求得表3的结果,表3给出了每辆车的具体行驶路线行车路线,行驶里程,装载量和到达客户的时间。

4. 结论

表4给出了番禺配送中心的成本优化效果对比,相比较于优化前,可以得出使用车辆数由原来的10辆减少到6辆,总成本也减少了1076.52元。可以看出在进行优化之前,番禺配送中心目前的车辆调度方案存在很大的问题,由于没有提前规划路径,导致车辆在行驶的过程中存在着迂回运输,路径规划不合理的问题,由此导致车辆行驶里程长,不能在客户规定的时间段到达客户处,从而使得客户服务水平下降。本文在基本VRPSDP模型的基础上,加入多车型和时间窗两个因素,以配送车辆总的成本为优化

Table 1. Distance between distribution centers and customer points and customer points

表1. 配送中心与客户点以及各客户点间的距离(km)

Table 2. Information on distribution centers and customer points

表2. 配送中心以及客户点信息

Figure 1. Genetic algorithm iterative process

图1. 遗传算法迭代过程

Table 3. Result of genetic algorithm calculation

表3. 遗传算法计算结果

Table 4. Panyu distribution center cost optimization effect

表4. 番禺配送中心成本优化效果

目标,给出T公司广州番禺配送中心同时取送货的运作模式。最后从番禺配送中心运营成本进行优化效果分析,将本文采用的同时取送货的模式得到的结果与之前采用的模式得到的结果进行比较分析,证明了本文的优化方案是切实可行并且具有明显的优化效果的。

文章引用

徐静. 带时间窗的多车型同时取送货车辆路径问题研究
Research on the Problem of Taking Delivery Vehicle Routes for Multiple Vehicles with Time Windows at the Same Time[J]. 管理科学与工程, 2018, 07(02): 125-131. https://doi.org/10.12677/MSE.2018.72015

参考文献

  1. 1. Dantzing, G. and Ramser, J. (1959) The Truck Dispatching Problem. Management Science, 6, 80-91. https://doi.org/10.1287/mnsc.6.1.80

  2. 2. Dethloff, J. (2001) Vehicle Routing and Reverse Logistics: The Vehicle Routing Problem with Simulatancous Delivery and Pick-Up. OR Spectrum, 23, 79-96. https://doi.org/10.1007/PL00013346

  3. 3. 陈静. 以运输成本最低为目标的同时取送货车辆路径优化研究[D]: [硕士学位论文]. 长春: 吉林大学, 2016.

  4. 4. 葛显龙, 许茂增, 王伟鑫, 等. 基于联合配送的城市物流配送路径优化[J]. 控制与决策, 2016(3): 503-512.

  5. 5. Serdar Tasan, A. and Gen, M. (2012) A Genetic Algorithm Based Approach to Vehicle Routing Problem with Simultaneous Pick-Up and Deliveries. Computers & Industrial Engineering, 62, 755-761. https://doi.org/10.1016/j.cie.2011.11.025

  6. 6. 王晓博, 任春玉, 李海晨. 多车型开放式车辆路线问题的混合启发式算法[J]. 计算机工程与应用, 2013, 49(7): 243-247.

  7. 7. 罗鸿斌. 多车场多车型车辆调度问题的改进粒子群算法[J]. 计算机工程与应用, 2014, 50(7): 251-253.

期刊菜单