带整箱装载和时间窗的车辆路径规划解决方案

### 带整箱装载和时间窗的车辆路径规划解决方案 在物流运输领域，集装箱在码头与客户之间的运输是航运公司提供的一项重要服务。这种运输包含进口和出口订单，虽然每个订单都是整箱运输，但进口和出口订单可以组合在一次行程中，以降低运输成本。本文将深入探讨如何解决带整箱装载和时间窗的车辆路径规划问题。 #### 1. 运输背景与问题提出 航运公司在（内陆）客户和港口之间运输集装箱，这为公司提供了优化成本的机会。自动化的精确方法可以探索所有可能的组合，进一步降低成本。运输主要通过卡车进行，但在有条件的情况下也会使用铁路和驳船进行大量内陆集装箱运输。 运输包括货物交付（进口）和货物提取（出口）。进口时，装满货物的集装箱需从一个地点交付给客户，客户清空后，空集装箱要么运往出口客户处重新装满，要么运往码头存放。港口或内陆码头的进入成本是运输的主要成本之一，因此目标是在进口服务后紧接着进行出口服务，即订单三角化，以减少卡车行驶的总距离，降低成本。 三角化有两种类型： - **标准三角化**：进口行程和出口行程连接到同一个仓库，如图 1(a) 所示。 - **多仓库三角化**：进口行程和出口行程属于两个不同的仓库，如图 1(b) 所示。 此外，还有一种底盘三角化方式，卡车可以将装有集装箱的拖车留在客户处，待任务完成后再派车取回。但这种方式在日本和欧洲通常不可行，因为卡车不一定具备此功能，且交换拖车需要相同类型的卡车。而在美国和墨西哥，存在留下拖车的可能性。 我们从一家航运公司获得了一天的运营数据，包括满箱的起点/终点、空箱的存放位置以及每个订单的服务时间窗。这些时间窗由客户设定，但如果航运公司能影响客户的时间窗选择，可能会更好地进行三角化。所有考虑的订单均为干货集装箱，有 20 英尺、40 英尺、20 英尺高和 40 英尺高四种不同尺寸。进口订单和出口订单在集装箱尺寸相同或进口订单的集装箱为高箱且进出口订单的集装箱英尺尺寸相同时可以进行三角化。 航运公司对空集装箱的存放位置可能有要求，目前空集装箱存放在满箱到达的港口，但这可能导致不必要的运输。若让车辆始终将空集装箱运往最近的集装箱堆场，可能会导致一些堆场集装箱溢出，而另一些堆场为空。 #### 2. 相关研究回顾 带交付和提取关联的整箱装载路径规划问题可视为带回程的车辆路径规划问题的简化版本。以往的研究中，Imai 等人研究了整箱装载三角化的车辆路径规划问题，但未考虑时间窗，他们使用基于拉格朗日松弛的启发式方法解决问题。Caris 和 Janssens 扩展了问题，考虑了时间窗，使用局部搜索启发式方法求解。 与以往研究不同的是，本文考虑了多个港口，出现了多仓库三角化情况，而之前的研究仅考虑了标准三角化。 #### 3. 数学模型构建 为了求解该问题，我们构建了以下数学模型。假设车辆车队是同质的，所有集装箱相同，每辆车的容量为一个集装箱。 定义以下参数和变量： - **参数**： - \(P\)：所有可能路径（行程模式）的集合 - \(K\)：所有订单的集合 - \(c_p\)：路径 \(p\) 的成本 - \(\alpha_{kp}\)：若路径 \(p\) 涵盖订单 \(k\)（满箱移动），则为 1 - \(\beta_{kp}\)：若路径 \(p\) 涵盖与订单 \(k\) 相关的空箱移动，则为 1 - \(O_k\)：订单 \(k\) 的需求 - \(a_{kp}\)：车辆 \(p\) 到达与订单 \(k\) 相关客户的时间 - \(d_{kp}\)：车辆 \(p\) 离开与订单 \(k\) 相关客户的时间 - \(s\)：填充或清空集装箱所需的时间 - **变量**： - \(y_p\)：二进制变量，若路径 \(p\) 被使用，则为 1 该问题可以表述为以下线性整数规划问题： **IP1**： \(\text{min} \sum_{p\in P} c_p y_p\) (1) \(\text{s.t.} \sum_{p\in P} \alpha_{kp} y_p = O_k, \forall k \in K\) (2) \(\sum_{p\in P} \beta_{kp} y_p = O_k, \forall k \in K\) (3) \(\sum_{p\in P} a_{kp} y_p + s \leq \sum_{p\in P} d_{kp} y_p, \forall k \in K\) (4) \(y_p \in \{0, 1\}\) (5) - **目标函数 (1)**：最小化总体路径成本。 - **约束条件 (2)**：确保在规划期内满足所有订单需求。 - **约束条件 (3)**：确保与订单相关的所有空箱提取和交付都完成。 - **约束条件 (4)**：对于出口订单，确保空箱在满箱出发前到达；对于进口订单，确保满箱在空箱被取走前到达。 - **约束条件 (5)**：定义变量的取值范围。 如果只考虑箱