车辆路径问题

2024-02-09 14:21| 来源: 网络整理| 查看: 265

车辆路径问题通常被定义为装运一系列点或接收点，通过他们组织车辆适当途径有序。在一定的约束条件，如对商品的需求，交货数量，交付的交付时间，车辆容量限制，行驶里程限制，时间限制，以实现某些目标。如果最短距离，最低的成本，尽可能少的时间，尽量少使用车辆。因为运输点、更多的客户、商品种类繁多，区域交通网络等诸多影响因素的不均匀分布使得在城市的运输路线，运输服务中加深了处理问题的复杂性。再加上如时间窗等客户提出的约束要求，使得如何安排最佳路线，如何使用有效的运输路线已成为难题。合理的解决车辆路径问题，不仅可以简化流通过程，缩短交货时间，降低负载率运载工具，以降低物流成本提高经济效率，加快响应客户需求的速度，提高服务质量，提升客户满意的物流环节。因此，物流配送车辆调度问题是在这个过程中的一个关键问题。

一、车辆路径问题的类型

车辆路径问题（VRP）最早是由 Dantzig 和 Ramser 于1959年首次提出，它是指一定数量的客户，各自有不同数量的货物需求，配送中心向客户提供货物，由一个车队负责分送货物，组织适当的行车路线，目标是使得客户的需求得到满足，并能在一定的约束下，达到诸如路程最短、成本最小、耗费时间最少等目的。经典VRP可描述为：对一系列装卸货点进行适当的路径规划，在满足约束条件（客户需求、车辆载重和容积、车型、车辆行驶里程、配送时间窗、配送中心数量等限制）和目标最优化（路程最短、成本最低、使用车辆数最少、配送时间最快等）下，将客户的配送需求从配送中心送达客户点，然后从客户点送回配送中心。实际应用中，车辆路径问题是由很多条件的限制。例如，首先，车辆容量限制总需求各车辆服务的客户，不得超过车辆的最大负载重量。二，时间窗的限制，每个客户端服务必须在一定的时间范围内。第三，物流公司可能对客户服务的多个配送中心。四，客户可能会返回部分商品的配送中心。第五，客户可以是不同的车辆服务。第六，客户需求和其他随机锻炼路线的数量。第七，服务订单的客户限制之间存在。在研究工作中，常常做出关于限制一些基本假设。如由一个配送中心，一个单一的模型来完成任务分配是商品的集散地混合每个客户的位置，并从配送中心到被称为他们的距离。配送中心有足够的货物交付，并有足够的运输能力，每个客户是汽车服务，也只能是对车辆的每一行需求的汽车服务必须不超过最大负载重量。所有车辆都从配送中心出发，完成任务的客户，最后回到配送中心。实际的分布也可以考虑多中心，多车，时间要求和客户需求的客户服务随机化等。对于一个特定的问题，所有的上述限制可能存在的，有可能是唯一的一个组成部分。

二、CVPR问题的数学模型

车辆路径问题（VRP）有非常多的变形，这里介绍VRP研究最多的基本问题——有容量约束的车辆路径问题（Capacitated Vehicle Routing Problem，CVRP）。在CVRP问题中，要求由一个车队承担将货物从一个仓库运输到其他预先指定的客户点上的任务。其中，车队的车辆都是同质的，且都只能从仓库出发，服务完客户点后，返回仓库。每个客户点也只能被一辆车访问一次。决策对象是车辆的行驶路线，每辆车在不同的路线上的行驶成本不同，最终的目标是要使得完成这个任务的车队的总成本最小。 CVRP问题具有下面特征

单向：纯取货/纯送货；单配送中心：只有一个配送中心/车场；单车型：只考虑一种车型；需求不可拆分：客户需求只能有一辆车满足；车辆封闭：完成配送任务的车辆需回到配送中心；车辆充足：不限制车辆数量，即配送车辆需求均能满足；非满载：任意客户点的需求量小于车辆最大载重。

符号说明

\(C_0\)、\(C_1\) 表示车辆启动的固定成本、单位距离的行驶成本 \(N\) 服务客户点数量，索引为\(i,j\) \(n\) 节点集合（\(n=0,1,2,\ldots, N\)），其中0表示配送中心；\(1,2,\ldots, N\)表示客户点 \(D\) 车辆行驶的最大距离 \(K\) 使用的最大车辆数 \(m\) 拥有的车辆数，索引为k \(d_{ij}\) 客户点\(i(x_i,y_i)\)和\(j (x_j,y_j)\) 的欧氏距离 \(m_j\) 第\(j\)个客户的需求量 \(M\) 车辆的最大载重

\[x_{ijk}= \begin{cases} 1, & 表示车辆k从客户点i行驶到客户点j \\ 0, & 其他\end{cases}\]

目标函数:

\[\operatorname{Min} Z=C_0 K+C_1 \sum_{j=0}^N \sum_{j=0}^N \sum_{k=1}^K d_{ij} x_{ijk} \]

约束: a. 配送中心约束: 所有车辆均由配送中心出发, 完成所有的配送任务后返回配送中心:

\[\sum_{k=1}^K \sum_{j=1}^N x_{0 j k}=\sum_{k=1}^K \sum_{j=1}^N x_{j 0 k}=K \]

b. 客户点流量平衡：进出车辆数相等

\[\sum_{i=1}^N x_{i j k}=\sum_{i=1}^N x_{j i k}(k \in m, \forall j=1,2, \ldots, N) \]

c. 重量约束: 每辆车的装载量不能超过其最大载重量限制

\[\sum_{i=0}^N \sum_{j=0}^N \mathrm{x}_{ijk} m_j \leq M(k \in m) \]

d. 客户点服务约束: 每个客户点被服务 1 次

\[\sum_{k=1}^K \sum_{i=0}^N x_{ijk}=1(j=1,2, \ldots, N) \]

e. 车辆行驶距离约束: 每辆车配送不超过最大配送距离

\[\sum_{i=0}^N \sum_{j=0}^N \mathrm{x}_{i j k} d_{i j} \leq \mathrm{D}(k \in m) \]

f. 所需车辆数约束:

\[K \geq\left\lceil\frac{\sum_{j=1}^N m_j}{M}\right\rceil\left(K=1,2, \ldots, N \right) \]

CVRP问题是TSP问题的拓展，车辆容量无限大的CVRP问题可认为是TSP问题，即一辆车就可以服务所有的客户。CVRP问题的求解与TSP问题的求解类似, CVRP问题的解为一组满足需求节点需求的多个车辆的路径集合。假设某物流网络中共有10个顾客节点，编号为1~10，一个车辆基地，编号为0，在满足车辆容量约束与顾客节点需求约束的条件下，此问题的一个可行解可表示为：[0-1-2-0,0-3-4-5-0,0-6-7-8-0,0-9-10-0]，即需要4个车辆来提供服务，车辆的行驶路线分别为0-1-2-0,0-3-4-5-0,0-6-7-8-0,0-9-10-0。由于车辆的容量固定，基地固定，因此可以将上述问题的解先表示为[1-2-3-4-5-6-7-8-9-10]的有序序列，然后根据车辆的容量约束，对序列进行切割得到若干车辆的行驶路线。

三、CVPR的求解

下图中黑色节点表示配送中心，蓝色节点表示送货客户服务点，节点旁边数据表示需完成的送货需求。每辆车的最大容量为15，最大行驶距离为250公里，从0点出发运送货物再回到0点。求完成所有节点需求时的车辆最短运输路线。（为简化计算，车辆启动成本 \(C_0\) 取30，车辆单位距离行驶成本\(C_1\) 取1）

import math import random import pandas as pd import matplotlib.pyplot as plt from matplotlib.pylab import mpl mpl.rcParams['font.sans-serif'] = ['SimHei'] # 添加这条可以让图形显示中文 def calDistance(CityCoordinates): ''' 计算城市间距离输入：CityCoordinates-城市坐标；输出：城市间距离矩阵-dis_matrix ''' dis_matrix = pd.DataFrame(data=None, columns=range(len(CityCoordinates)), index=range(len(CityCoordinates))) for i in range(len(CityCoordinates)): xi, yi = CityCoordinates[i][0], CityCoordinates[i][1] for j in range(len(CityCoordinates)): xj, yj = CityCoordinates[j][0], CityCoordinates[j][1] dis_matrix.iloc[i, j] = round(math.sqrt((xi - xj) ** 2 + (yi - yj) ** 2), 2) return dis_matrix def greedy(CityCoordinates, dis_matrix): ''' 贪婪策略构造初始解,初始化时将VRP简化为TSP进行构造。输入：CityCoordinates-节点坐标,dis_matrix-距离矩阵输出：初始解-line ''' # 修改dis_matrix以适应求解需要 dis_matrix = dis_matrix.astype('float64') for i in range(len(CityCoordinates)): dis_matrix.loc[i, i] = math.pow(10, 10) dis_matrix.loc[:, 0] = math.pow(10, 10) # 0不在编码内 line = [] # 初始化 now_city = random.randint(1, len(CityCoordinates) - 1) # 随机生成出发城市 line.append(now_city) # 添加当前城市到路径 dis_matrix.loc[:, now_city] = math.pow(10, 10) # 更新距离矩阵，已经过城市不再被取出 for i in range(1, len(CityCoordinates) - 1): next_city = dis_matrix.loc[now_city, :].idxmin() # 距离最近的城市 line.append(next_city) # 添加进路径 dis_matrix.loc[:, next_city] = math.pow(10, 10) # 更新距离矩阵 now_city = next_city # 更新当前城市 return line def calFitness(birdPop, Demand, dis_matrix, CAPACITY, DISTABCE, C0, C1): ''' 贪婪策略分配车辆（解码），计算路径距离（评价函数）输入：birdPop-路径，Demand-客户需求,dis_matrix-城市间距离矩阵，CAPACITY-车辆最大载重,DISTABCE-车辆最大行驶距离,C0-车辆启动成本,C1-车辆单位距离行驶成本；输出：birdPop_car-分车后路径,fits-适应度 ''' birdPop_car, fits = [], [] # 初始化 for j in range(len(birdPop)): bird = birdPop[j] lines = [] # 存储线路分车 line = [0] # 每辆车服务客户点 dis_sum = 0 # 线路距离 dis, d = 0, 0 # 当前客户距离前一个客户的距离、当前客户需求量 i = 0 # 指向配送中心 while i < len(bird): if line == [0]: # 车辆未分配客户点 dis += dis_matrix.loc[0, bird[i]] # 记录距离 line.append(bird[i]) # 为客户点分车 d += Demand[bird[i]] # 记录需求量 i += 1 # 指向下一个客户点 else: # 已分配客户点则需判断车辆载重和行驶距离 if (dis_matrix.loc[line[-1], bird[i]] + dis_matrix.loc[bird[i], 0] + dis

【本文地址】

车辆路径问题

车辆路径问题

今日新闻

推荐新闻