取送货车辆路径规划问题

取送货车辆路径规划问题（Vehicle Routing Problems with Pickups and Deliveries，VRPPD）指的是货物再pickup points和delivery pionts之间的运输。可再将其分为两类。

  1. 第一类，pickup points和delivery pionts是unpaired的，即从某一pickup point出发，完成任一delivery point的需求即可。
  2. 第二类，pickup points和delivery pionts是paired的，即某项运输需求有指定的pickup point和指定的delivery point。第二类下在分类有classical Pickup and Delivery Problem (PDP)和Dial-A-Ride Problem (DARP)。PDP和DARP区别是：PDP运输的是货物，DARP运输的乘客。
    以上所述如下图在这里插入图片描述

取送货问题

取送货问题（Pickup and Delivery Problem，PDP）为一种点对点运输，即客户提供物流信息要求货运公司派车至指定点取货再送至另一指定点卸货。具有时间窗限制的取送货问题( Pickup and Delivery Problem with Time Windows，PDPTW)

列生成算法求解PDPTW问题

问题描述

PDPTW相关概念描述如下：

  1. 任务：货运公司接到客户订单( 货运需求) 后，即产生一个取货任务与一个送货任务。在路网 中，一取货任务代表一取货点，一送货任务代表一 送货点。
  2. 巡回路径: 每辆货车从场站出发后执行一 连串的任务，最终再回到场站的路径称为巡回路径，简称路径。
  3. 优先级约束: 针对每一货运需求，取货任 务的服务顺序须于送货任务前。
  4. 联结约束: 每一货运需求的取送货任务均 由同一辆车服务。
  5. 时间窗约束: 每个取送货任务均有允许服 务的时间范围，车辆仅能于该范围内执行任务，若 早于时间范围到达，则需等待至最早开始时间; 若 晚于时间范围，则不可执行该客户的任务。
  6. 车辆容量约束: 配送车辆有载重上限，作 业过程中不可违反车辆容量限制。

PDPTW 问题可以描述为: 客户需求包括取货 作业与送货作业两部分，车辆由场站空驶出发，到达客户指定的取货点收取货物后运送至客户指定 的送货点，各作业任务均有时间窗限制，任务完成 后车辆回到场站。

符号说明

xrx_rxr​  0-1变量，代表一条可行路径，满足时间窗约束、车辆容量约束、优先级约束、联结约束。当路径rrr被选择，则xr=1x_r=1xr​=1，反之，xr=0x_r=0xr​=0。
RRR   为所有路径的集合。
CrC_rCr​  选择路径rrr的成本。
NNN  任务节点结合。
aira_{ir}air​  路径rrr包含任务iii，若路径rrr包含任务iii，则air=1a_{ir}= 1air​=1，反之air=0a_{ir}= 0air​=0

集合覆盖模型(set covering model)

min∑r∈RCrxr(1)min\sum_{r \in R}C_rx_r \tag{1}minr∈R∑​Cr​xr​(1) ∑r∈Rairxr≥1,∀i∈N(2)\sum_{r \in R}a_{ir}x_r \geq 1, \forall i \in N \tag{2}r∈R∑​air​xr​≥1,∀i∈N(2) ∑r∈Rxr≤K(3)\sum_{r \in R}x_r \leq K \tag{3}r∈R∑​xr​≤K(3) xr∈{0,1},∀r∈R(4)x_r\in \{0,1\}, \forall r \in R \tag{4}xr​∈{0,1},∀r∈R(4)

式（1）为最小化所有路径的总行驶距离成本
式（2）表示每一个任务iii都至少被服务一次
式（3）为车辆数目约束，KKK为可使用车辆数的上限
式（4）0-1变量

主问题（MP）

松弛集合覆盖模型的式（4）：
min∑r∈RCrxr(5)min\sum_{r \in R}C_rx_r \tag{5}minr∈R∑​Cr​xr​(5) ∑r∈Rairxr≥1,∀i∈N(6)\sum_{r \in R}a_{ir}x_r \geq 1, \forall i \in N \tag{6}r∈R∑​air​xr​≥1,∀i∈N(6) ∑r∈Rxr≤K(7)\sum_{r \in R}x_r \leq K \tag{7}r∈R∑​xr​≤K(7) xr≥0,∀r∈R(8)\color{red}{x_r \geq 0, \forall r \in R \tag{8}}xr​≥0,∀r∈R(8)
式（5）为最小化所有路径的总行驶距离成本
式（6）表示每一个任务iii都至少被服务一次
式（7）为车辆数目约束，KKK为可使用车辆数的上限
式（8）松弛整肃约束后的非负限制

限制主问题（RMP）

min∑r∈R′Crxr(9)min\sum_{r \in R'}C_rx_r \tag{9}minr∈R′∑​Cr​xr​(9) ∑r∈R′airxr≥1,∀i∈N(10)\sum_{r \in R'}a_{ir}x_r \geq 1, \forall i \in N \tag{10}r∈R′∑​air​xr​≥1,∀i∈N(10) ∑r∈R′xr≤K(11)\sum_{r \in R'}x_r \leq K \tag{11}r∈R′∑​xr​≤K(11) xr≥0,∀r∈R′(12)\color{black}{x_r \geq 0, \forall r \in R' \tag{12}}xr​≥0,∀r∈R′(12)
其中，R′⊆R,R′≪RR' \subseteq R, R'\ll RR′⊆R,R′≪R

限制主问题的对偶问题

其中：
πi\pi_iπi​：非负对偶变量，对应约束(10)(10)(10)
π0\pi_0π0​：非负对偶变量，对应约束(11)(11)(11)

max∑i∈Nπi+Kπ0(13)max\sum_{i \in N}\pi_i+K\pi_0 \tag{13}maxi∈N∑​πi​+Kπ0​(13) ∑i∈Nairπi+π0≤C,∀r∈R′(14)\sum_{i \in N}a_{ir}\pi_i +\pi_0 \leq C, \forall r \in R' \tag{14}i∈N∑​air​πi​+π0​≤C,∀r∈R′(14) πi≥0,∀i∈N(15)\pi_i \geq 0 , \forall i \in N \tag{15}πi​≥0,∀i∈N(15) π0≤0(16)\pi_0 \leq 0 \tag{16}π0​≤0(16)

子问题

Cr−∑i∈Nairπi−π0<0C_r-\sum_{i\in N}a_{ir} \pi_i-\pi_0<0Cr​−i∈N∑​air​πi​−π0​<0

# 人工智能
Logo
魔乐社区

魔乐社区（Modelers.cn) 是一个中立、公益的人工智能社区，提供人工智能工具、模型、数据的托管、展示与应用协同服务，为人工智能开发及爱好者搭建开放的学习交流平台。社区通过理事会方式运作，由全产业链共同建设、共同运营、共同享有，推动国产AI生态繁荣发展。

更多推荐

cover

全家桶集齐！Qwen3.5四款小模型上线魔乐社区，附昇腾全套实践教程

avatar 魔乐社区

Pont - 搭建前后端之桥：高效、灵活的接口管理工具

Pont 是一款强大的数据服务层解决方案，它能够帮助开发者快速搭建前后端之间的桥梁，实现接口的高效管理和代码自动生成。无论是新手还是有经验的开发者，都能通过 Pont 轻松处理接口文档、生成类型安全的 API 代码，从而显著提升开发效率。[![Pont 工具标志](https://raw.gitcode.com/gh_mirrors/po/pont/raw/3f1b7d4bbba3fd2dda

avatar 魔乐社区

如何快速上手 hvac：HashiCorp Vault Python 客户端零基础入门指南

**hvac** 是 HashiCorp Vault 的 Python 3.X 客户端库，专为开发者提供简单高效的 Vault 交互方式。无论你是需要管理密钥、配置身份验证，还是实现安全的秘密数据存储，hvac 都能帮助你轻松搞定 Vault 的各项操作。本文将带你零基础快速入门，从安装到基础操作，让你在几分钟内即可上手使用这个强大的工具。[![hvac 客户端 Logo](https://r

avatar 魔乐社区