强化学习解决VRP：单模型优化的车辆路线问题
需积分: 9 95 浏览量
更新于2024-09-07
收藏 325KB PDF 举报
本文主要探讨了在人工智能顶级会议（AI-VRP顶会）中，如何利用强化学习（Reinforcement Learning, RL）解决车辆路线问题（Vehicle Routing Problem, VRP）。VRP是一个经典的优化问题，涉及寻找最有效的货物配送路径，以最小化成本或时间，同时满足车辆的容量限制。传统的解决方法通常依赖于精确的数学模型和优化算法，如遗传算法、模拟退火等。
作者们提出了一种端到端的框架，通过训练单一的策略模型来应对各种规模相似的VRP实例。他们采用参数化的随机策略，这种策略允许模型根据环境反馈（奖励信号）动态调整其决策，遵循可行性规则，从而找到接近最优解的解决方案。值得注意的是，这个模型是通过应用一种政策梯度算法来优化其参数的，这意味着在训练完成后，模型可以直接实时生成解决方案，而无需针对每个新的问题实例重新训练，提高了效率。
实验结果显示，当处理有容量限制的VRP时，他们的方法在中型规模问题上，在解决方案质量上优于传统的启发式算法，如局部搜索算法，并且与Google的OR-Tools在计算时间上具有可比性。此外，该研究还展示了如何将分批交付（split delivery）这一复杂的现实世界特性纳入VRP的解决策略中，并探讨了这种方法在处理这类问题时的效果。
这篇论文提供了一个创新的RL在VRP中的应用实例，证明了通过机器学习技术可以实现高效且灵活的解决方案生成，这对于实际物流和运输规划具有重要的实践价值。它不仅提升了问题求解的效率，还展示了机器学习在解决复杂优化问题上的潜力和优势。未来的研究可能会进一步探索如何将这种方法扩展到更大规模的问题，或者与其他优化技术结合，以达到更优的性能。
of these models. The general architecture, which is shared by many of these models, consists of
two RNN networks called the encoder and decoder. An encoder network reads through the input
sequence and stores the knowledge in a fixed-size vector representation (or a sequence of vectors);
then, a decoder converts the encoded information back to an output sequence.
In the vanilla Sequence-to-Sequence architecture [
32
], the source sequence appears only once in the
encoder and the entire output sequence is generated based on one vector (i.e., the last hidden state
of the encoder RNN). Other extensions, for example Bahdanau et al.
[3]
, illustrate that the source
information can be used more explicitly to increase the amount of information during the decoding
steps. In addition to the encoder and decoder networks, they employ another neural network, namely
an attention mechanism that attends to the entire encoder RNN states. This mechanism allows the
decoder to focus on the important locations of the source sequence and use the relevant information
during decoding steps for producing “better” output sequences. Recently, the concept of attention has
been a popular research idea due to its capability to align different objects, e.g., in computer vision
[
6
,
18
,
39
,
40
] and neural machine translation [
3
,
19
,
25
]. In this study, we also employ a special
attention structure for the policy parameterization. See Section 3.3 for a detailed discussion of the
attention mechanism.
Neural Combinatorial Optimization
Over the last several years, multiple methods have been
developed to tackle combinatorial optimization problems by using recent advances in artificial
intelligence. The first attempt was proposed by Vinyals et al.
[34]
, who introduce the concept of
a Pointer Network, a model originally inspired by sequence-to-sequence models. Because it is
invariant to the length of the encoder sequence, the Pointer Network enables the model to apply to
combinatorial optimization problems, where the output sequence length is determined by the source
sequence. They use the Pointer Network architecture in a supervised fashion to find near-optimal
Traveling Salesman Problem (TSP) tours from ground truth optimal (or heuristic) solutions. This
dependence on supervision prohibits the Pointer Network from finding better solutions than the ones
provided during the training.
Closest to our approach, Bello et al.
[4]
address this issue by developing a neural combinatorial
optimization framework that uses RL to optimize a policy modeled by a Pointer Network. Using
several classical combinatorial optimization problems such as TSP and the knapsack problem, they
show the effectiveness and generality of their architecture.
On a related topic, Dai et al.
[11]
solve optimization problems over graphs using a graph embedding
structure [
10
] and a deep Q-learning (DQN) algorithm [
26
]. Even though VRP can be represented
by a graph with weighted nodes and edges, their proposed approach does not directly apply since in
VRP, a particular node (e.g. the depot) might be visited multiple times.
Next, we introduce our model, which is a simplified version of the Pointer Network.
3 The Model
In this section, we formally define the problem and our proposed framework for a generic combinato-
rial optimization problem with a given set of inputs
X
.
= {x
i
, i = 1, · · · , M}
. We allow some of
the elements of each input to change between the decoding steps, which is, in fact, the case in many
problems such as the VRP. The dynamic elements might be an artifact of the decoding procedure
itself, or they can be imposed by the environment. For example, in the VRP, the remaining customer
demands change over time as the vehicle visits the customer nodes; or we might consider a variant
in which new customers arrive or adjust their demand values over time, independent of the vehicle
decisions. Formally, we represent each input
x
i
by a sequence of tuples
{x
i
t
.
= (s
i
, d
i
t
), t = 0, 1, · · · }
,
where
s
i
and
d
i
t
are the static and dynamic elements of the input, respectively, and can themselves
be tuples. One can view
x
i
t
as a vector of features that describes the state of input
i
at time
t
. For
instance, in the VRP,
x
i
t
gives a snapshot of the customer
i
, where
s
i
corresponds to the 2-dimensional
coordinate of customer
i
’s location and
d
i
t
is its demand at time
t
. We will denote the set of all input
states at a fixed time t with X
t
.
We start from an arbitrary input in
X
0
, where we use the pointer
y
0
to refer to that input. At every
decoding time
t
(
t = 0, 1, · · ·
),
y
t+1
points to one of the available inputs
X
t
, which determines
the input of the next decoder step; this process continues until a termination condition is satisfied.
The termination condition is problem-specific, showing that the generated sequence satisfies the
3
剩余10页未读，继续阅读
2021-09-11 上传
2021-05-14 上传
2021-10-10 上传
2021-09-30 上传
2021-10-02 上传
2021-05-14 上传
qq_42916478
- 粉丝: 0
- 资源: 1
我的内容管理
展开
最新资源
- 黑板风格计算机毕业答辩PPT模板下载
- CodeSandbox实现ListView快速创建指南
- Node.js脚本实现WXR文件到Postgres数据库帖子导入
- 清新简约创意三角毕业论文答辩PPT模板
- DISCORD-JS-CRUD：提升 Discord 机器人开发体验
- Node.js v4.3.2版本Linux ARM64平台运行时环境发布
- SQLight：C++11编写的轻量级MySQL客户端
- 计算机专业毕业论文答辩PPT模板
- Wireshark网络抓包工具的使用与数据包解析
- Wild Match Map: JavaScript中实现通配符映射与事件绑定
- 毕业答辩利器：蝶恋花毕业设计PPT模板
- Node.js深度解析：高性能Web服务器与实时应用构建
- 掌握深度图技术：游戏开发中的绚丽应用案例
- Dart语言的HTTP扩展包功能详解
- MoonMaker: 投资组合加固神器，助力$GME投资者登月
- 计算机毕业设计答辩PPT模板下载
