# Reinforcement Learning for Multi-Truck Vehicle Routing Problems

Randall Correll  QC Ware Corp., Palo Alto, CA USA  Sean J. Weinberg  QC Ware
Corp., Palo Alto, CA USA  Fabio Sanches  QC Ware Corp., Palo Alto, CA USA
Takanori Ide  AISIN CORPORATION, Tokyo Research Center, Chiyoda-ku, Tokyo,
Japan  Takafumi Suzuki  Aisin Technical Center of America, San Jose, CA USA

###### Abstract

Vehicle routing problems and other combinatorial optimization problems have
been approximately solved by reinforcement learning agents with policies based
on encoder-decoder models with attention mechanisms. These techniques are of
substantial interest but still cannot solve the complex routing problems that
arise in a realistic setting which can have many trucks and complex
requirements. With the aim of making reinforcement learning a viable technique
for supply chain optimization using classical computing today and quantum
computing in the future, we develop new extensions to encoder-decoder models
for vehicle routing that allow for complex supply chains. We make two major
generalizations. First, our model allows for routing problems with multiple
trucks. Second, we move away from the simple requirement of having a truck
deliver items from nodes to one special depot node, and instead allow for a
complex tensor demand structure. We show how our model, even if trained only
for a small number of trucks, can be embedded into a large supply chain to
yield viable solutions.

##  I Introduction

In the setting of commercial operations, computational problems of substantial
theoretical and practical difficulty regularly arise. Even a small improvement
on the quality of solutions to such problems can translate to a very
substantial benefit. One such problem, heavily studied in operations research,
is the vehicle routing problem [1, 2].

Vehicle routing problems are NP-hard combinatorial optimization problems for
which there are numerous heuristic algorithms which yield approximate
solutions. Relatively recently, there has been interest in solving such
routing problems using reinforcement learning (RL) [3]. In this context, a
truck driving between nodes can be thought of as an agent performing actions
(selecting its next node to drive to) in the environment of the supply chain.
This approach has been successful for a wide range of combinatorial
optimization problems, especially when using models with an encoder-decoder
attention mechanisms [4].

In a sense, the use of reinforcement learning for such problems is very
natural. RL is appropriate in contexts where decisions must be made with
complex consequences can only be learned through experience. Games like Go
naturally fit that description, and indeed they have been well-addressed with
RL methodology [5]. More easily overlooked is that the routing of a truck
through a supply chain is in many ways similar to a game like Chess or Go. The
“moves” in this game are the selections of where to drive, what to pick up,
and what to drop off. The consequences of these moves are complicated and can
have long-term effects that are best learned through experience.

Unfortunately, reinforcement learning approaches for combinatorial
optimization are not readily deployed in a commercial setting because of
simplifications that they make. For the vehicle routing problem in particular,
past work has largely focused on the case of a single truck with a simple
task: bring “demand” from nodes to a depot. In reality, supply chains involve
numerous trucks, and requirements are more complex than simply bringing
material to one depot node, and the current machine learning models are not
equipped to handle such complex situations.

In this work, we take steps toward developing RL agents that can obtain good
solutions in complex supply chains. We use as our model a real commercial
supply chain of Aisin Corporation, a Japanese automotive manufacturing
company. We build on the work of [4] by adding new techniques allowing for
multiple trucks and for far more general requirements for trucks. While our
model is specially designed with Aisin Corporation’s vehicle routing problems
in mind, our techniques for applying RL to a very general class of routing
problems apply widely.

##  II Vehicle Routing Problems

This section describes the particular vehicle routing problem that we apply a
reinforcement learning method to solve as well as the full-scale logistical
problem that it is based on.

Broadly speaking, vehicle routing problems (VRPs) [1, 2] are combinatorial
optimization problems where one or more trucks must carry material between
locations to accomplish certain requirements subject to constraints like
capacity and time limitations. There are numerous variants of VRPs so “vehicle
routing problem” is an umbrella term rather than a specific computational
problem.

The three subsections below describe VRPs of gradually increasing complexity.
Section II.1 reviews standard vehicle routing problems for which there are
already many solution methods including reinforcement learning. Section II.2
describes a more general form of VRP that we use as the environment for our
reinforcement learning agent. Unlike the basic VRP, the general VRP allows for
multiple trucks and all-to-all connectivity for demand structure. Finally,
section II.3 describes a real routing problem encountered by Aisin
Corporation. This real routing problem is quite similar to the general VRP of
section II.2, but includes additional constraints that are difficult to model
on a GPU.

###  II.1 Basic Vehicle Routing Problems

In this section, we review the the capcitated vehicle routing problem with
split-deliveries (SDVRP). We use the term “basic VRP” to refer to this problem
because it can be thought of as the base-model from which we generalize.

For the SDVRP, we are given a graph where nodes $z_{0},z_{1},\ldots z_{n}$ are
locations and weighted directed edges are the times needed to drive between
the locations. One of the nodes ,$z_{0}$, is special and is called the depot.
To every non-depot node $i$, there is a certain nonnegative real number
$d_{i}$ called the demand for node $i$. A truck, which starts at the depot,
must drive between the nodes, pick up demand, and return it to the depot. The
truck has limited capacity $1$ so it may need to make multiple trips to the
depot.

To be precise, an instance of the basic VRP is specified by:

  1. 1.

A graph $G$ with $n+1$ nodes $z_{0},z_{1},\ldots,z_{n}$.

  2. 2.

An $n+1\times n+1$ matrix $T$ with non-negative entries and $T_{ii}=0$ for all
$i\in\\{0,1,\ldots,n\\}$ called the _time matrix_.

  3. 3.

A non-negative number $d_{i}$ assigned to each node $z_{i}$ except for the
depot ($i\neq 0$). These numbers are called _initial demands._

The nodes of the graph can be abstract, but in many cases they are explicitly
given as coordinates for locations that trucks might drive to. The time matrix
entry $T_{ij}$ is supposed to be the time it take a truck to drive from node
$i$ to node $j$. That is why we require $T_{ii}=0$. The initial demand $d_{i}$
is supposed to be the amount of material111“Amount of material” is
intentionally vague. In a practical application, demand can be quantified by
geometrical volume, by weight, or even by monetary value. For our purposes, we
will use geometrical volume as the standard meaning for “amount of material”
which makes it sensible that trucks have a limited carrying capacity. that
must be carried by a truck from the node $z_{j}$ to the depot node $z_{0}$.

A candidate solution to this VRP is given by a route: a list of integers
$\xi=\xi_{1},\xi_{2},\ldots,\xi_{k}$ where $k$ is some positive integer
(called the route length) and each $\xi_{j}$ is an element of
$\\{0,1,\ldots,n\\}$. We require that $\xi_{1}=0$ and $\xi_{k}=0$ so that the
truck starts and ends at the depot. Given such a sequence, there are two
questions:

  * •

What is the total driving time for $\xi$?

  * •

Is $\xi$ a demand-satisfying route?

Here, the driving time for the route $\xi$ is defined as

$\text{time}(\xi)=\sum_{t=1}^{k-1}T_{\xi_{t}\xi_{t+1}}.$ (1)

Meanwhile, the question of whether or not the route is demand-satisfying is
intuitive but not mathematically elegant to describe. In short, a route is
demand satisfying if it will result in a truck carrying all of the initial
demand to the depot. The truck which starts at $\xi_{1}$ and follows the route
has a _capacity_ which we always take to be 1. This is the amount of demand
that the truck can store. The amount of demand the truck is carrying at a
given time is called _on-board demand_ to distinguish it from _off-board_
demand which is the dynamical demand waiting to be picked up at each node. As
the truck navigates its route, it picks up as much demand as
possible222Actually, we might decide to not pick up the full demand at a given
node by optimizing a pickup-selection algorithm, but we don’t consider this
case here. at each stop, converting off-board demand to on-board demand. The
on-board demand is never allowed to exceed 1. When the truck returns to the
depot, the on-board demand is reset to 0, and the route can continue until all
off-board demand is zero and the truck as at the depot.

The optimization goal of this basic vehicle routing problem is to find, among
all demand-satisfying routes, the one with minimal driving time.

The usage of reinforcement learning for this split-delivery vehicle routing
problem is well-established in the literature [4]. In fact, the model we use
is a generalization of that of Kool _et al._ our

###  II.2 Generalized Vehicle Routing Problems

We now turn to a generalization of the basic vehicle routing problem which is
inspired by the realistic supply chain optimization problem of Aisin
Corporation that we explain in detail in section II.3. The purpose of the
“general VRP” is to find a middle ground between the overly simple basic VRP
and the enormously complex Aisin Corporation VRP. This middle ground has major
features of the full-scaled supply chain logistics problem, but does not
include some messy constraints that are difficult to simulate efficiently for
training.

There are two ways that the general VRP is more complex than the basic
variant:

  1. 1.

There are multiple trucks.

  2. 2.

There is no special depot. Instead, demand is required to be moved between
specific nodes with various constraints. We refer to this as a _tensor demand
structure_ and explain it in detail below.

The use of multiple trucks is an obvious challenge for any routing algorithm
as optimal routes can involve subtle collaboration between trucks. Less
obvious is the surprisingly complex issue of tensor demand structure, where
any node can be a depot. For both these new ingredients, we have developed
modifications to the encoder and decoder models of [4].

#### Tensor Demand Structure

The basic VRP discussed in section II.1 has the property that all demand must
be taken to the same destination node (the depot). This is built into the
mathematical description of the problem because the off-board demand has a
_vector demand structure_. This means that the demand at a given time step $t$
is given by a vector

$d^{t}=\left(d_{1}^{t},d_{2}^{t},\ldots,d_{n}^{t}\right).$

In a realistic supply chain, we do not have the luxury of a single delivery
destination. Goods from a given node may be split into groups which need to be
taken to various delivery destination nodes. To accommodate such a situation,
we introduce the concept of a _tensor demand structure_. We begin with a
rank-2 tensor.

#### Rank-2 Demand

Assume that there is only one truck and consider a graph with $n$ nodes
$z_{1},\ldots,z_{n}$. (There is no longer any need for a special $z_{0}$
node). We introduce an $n\times n$ matrix $D^{t=0}$ with non-negative entries.
The meaning of the entry $D_{ij}^{0}$ is, intuitively, the initial amount of
demand that is located at node $i$ and must be shipped to node $j$. $D$ is
referred to as rank-2 off-board demand or as a matrix demand structure.

When the truck arrives at node $i$ at time $t$ with this sort of demand
structure, an issue arises: a _pickup selection_ decision must be made. There
are $n$ different types of demand that can be picked up from node $i$:
$\left(D_{i1}^{t-1},D_{i2}^{t-1},\ldots,D_{in}^{t-1}\right).$ There is not an
obvious way to perform pickup selection. In principle, a reinforcement
learning agent could learn optimal pickup selection, but this is beyond the
scope of our work. We assume that some reasonable selection algorithm is used.

After pickup selection, we obtain a new matrix $D^{t}$ by reducing $D^{t-1}$
by the amount of demand picked up by the truck from node $i$. Another issue
now appears: with demand on the truck, we have to remember which parts of the
on-board demand must go to which destination nodes. This can be dealt with by
promoting on-board demand at time $t$ to a vector
$E^{t}=\left(E_{1}^{t},E_{2}^{t},\ldots,E_{n}^{t}\right)$. The meaning of
$E_{i}^{t}$ is that, after the operations at time step $t$ (including pickup),
$E_{i}^{t}$ is the amount of demand on the truck which must be delivered to
node $i$.

Now that there is on-board demand in the truck, we need to revisit what
happens when the truck first arrives at a given node $i$. Before pickup
selection or any other operation, the first step is now to completely drop off
demand $E_{i}^{t-1}$. Mathematically, this simply means setting $E_{i}^{t}=0$.
If we wish, we can also keep track of the overall total demand satisfied after
each time step, in which case we would iteratively defined a sequence $S$ by

$\displaystyle S^{0}$ $\displaystyle=0,$ $\displaystyle S^{t}$
$\displaystyle=S^{t-1}+E_{\xi_{t}}^{t-1},$

where $\xi_{t}$ refers to the node visited at time step $t$.

#### Arbitrary Rank Demand

The ideas of a demand matrix $D_{ij}^{t}$ can readily be generalized to
higher-rank tensors. The reason for doing this is that in a practical supply
chain (including the one our study is based on), there are delivery
requirements along the lines of “move this box from node 3 to node 7, and then
from node 7 to node 5”. Such multi-leg requirements may sound odd, but they
can arise for numerous practical reasons. There may be capacity limitations at
node 5, and node 7 may be a storage warehouse. Or perhaps the box needs to
have an operation performed on it before its final delivery. Another important
reason for multi-leg delivery requirements is that a cargo container may need
to be sent somewhere else after delivery.

Whatever the reason, there promoting the matrix and vector structure of $D$
and $E$ to higher rank tensors allows us to encode the data that we need for
this new situation. An initial demand tensor $D_{ijk}^{0}$ can be interpreted
as “there is initially demand $D_{ijk}^{0}$ located at node $i$ which needs to
first travel to node $j$ and then travel to node $k$.”

Unfortunately, with higher-rank tensor structure like this, the operations
that are performed when a truck arrives at a node become even more
complicated. Consider first an empty truck arriving at node $i$ at time $t$.
It starts by performing pickup selection to decide what off-board to pick up:
any part of $D_{ijk}^{t-1}$ is fine as long as the first index is $i$. After
the pickup, the off-board demand is correspondingly reduced. However, the
loaded demand is now material with instructions like “go to node $j$, then go
to node $k$” so we must introduce a matrix on-board demand $E_{jk}^{t}$ to
track this. However, now that the truck has this on-board demand, when it
later drives to node $j$, the on-board $E_{jk}$ will be dropped off. This
demand is _not satisfied_ because it hasn’t reached its final destination of
node $k$. We are therefore forced to introduce a rank-2 matrix off-board
demand structure when this demand is dropped off! When that matrix off-board
demand is later picked up, it is converted to rank-1 vector on-board demand.

In conclusion, rank-$r$ off-board demand will automatically require tracking
off-board demands with ranks 2 through $r$as well as on-board demands with
ranks $1$ through $r-1$. These can be separately tracked by a collection of
tensors like

$\displaystyle D^{r\,t}$ $\displaystyle D^{r-1\,t}$ $\displaystyle\quad
E^{r-1\,t}$ $\displaystyle\vdots$ $\displaystyle D^{2\,t}$ $\displaystyle\quad
E^{2\,t}$ $\displaystyle\quad E^{1\,t}$

or, alternatively, we can use “diagonal entries” like $D_{ijj}$ instead of
$D_{ij}$. Regardless of the organizational approach, there is no question that
bookkeeping is one of the major issues that arise when dealing with this more
realistic version of a vehicle routing problem.

As with the cases above, we can introduce a “total demand satisfied” sequence
$S^{t}$ which accumulates only when demand is sent to its final destination.
We do not accumulate $S$ when rank-2 on-board demand arrives at a node, but we
do accumulate it when rank-1 on-board demand arrives because that node is the
final destination for that material.

#### Multiple Trucks

The next complexity to consider is the involvement of multiple trucks. This is
intuitive and easy to describe mathematically, but it adds immense difficulty
for optimization.

The main observation to make about the mathematical structure is that there is
an on-board demand for every truck, but there is only one off-board demand.
Thus, we need a new index $m$, which ranges from $1$ to the number of trucks
$N$, added to on-board demand. For instance:

$E_{ij}^{t,m}$

for rank-2 on-board demand. In this notation, we are dropping the $r=2$ symbol
as it is implied by the fact that there are two lower indices ($i$ and $j$).
In fact, because the notation involves so many indices, we will occasionally
also drop the reference to time as well. To help clarify, we use notation like

$E_{ij}^{m=2}$

to refer to rank 2 on-board demand for truck 2 in cases where we leave time
$t$ implicit. In other words, we explicitly write “$m=$” to indicate that we
are referring to truck number which ranges from $1$ to $N$.

In general, different trucks to have different capacities
$C_{1},\ldots,C_{N}$, but throughout our work we assume that all trucks have
capacity $1$. There is very little difficulty in adding varying capacities to
our models if needed.

The introduction of multiple trucks adds great subtleties to the problem. The
optimal solution to an instance with many trucks may involve highly
collaborative relationships between trucks.

Figure 1: Illustration of rank-2 cyclic off-board demand. At top, a package at
node 2 is waiting to be picked up. The package is to be sent to node 5 and
then returned. This contributes to $D^{\text{cyclic}}_{2\,5}$. After being
picked up by truck #1 (middle), the truck need not immediately travel to node
5. There is now a contribution to rank-2 on-board demand (and the cyclic
demand is gone). After dropping off the box at node 5, the empty box is still
required to go to node 2, contributing to rank-2 _direct_ demand while waiting
to be picked up.

#### Cyclic Demand Structure

The mathematical structure above is sufficient to describe another closely
related scenario with very little modification. In some commercial logistics
problems, trucks are required not only to deliver material but to then _return
empty containers back to the origin location_. This constraint is particularly
common for operations that occur in a repeating manner: trucks may need to
make regular (e.g. daily or weekly) shipments of identical items, and the same
specialized containers may need to be used. We allow for this constraint in
our general VRP.

Mathematically, we regard an empty box as no different from a full box as it
occupies the same amount of space in a truck.333Here, we are using volume as
the metric limited by truck capacity. We do not consider models constrained by
both weight and volume. The most straightforward way to enforce a box return
constraint is to simply increase the rank of tensor demand by one. However,
there is a more memory-efficient approach: we introduce a concept of _cyclic
off-board demand_. Meanwhile, we use the term _direct off-board demand_ to
refer to the sort of demand described earlier.

As an example of cyclic off-board demand, consider figure 1 in which material
initially at node 2 must be brought to node 5 before being returned to node 2.
We encode this demand as a term in a rank-2 tensor:
$D^{\text{cyclic}}_{2\,5}$. When a truck stops at node 2 to pick up this
cyclic demand, something different happens from the case of picking up direct
demand: the demand is converted to rank-2 on-board demand rather than rank 1.
Specifically, such a pickup of $D^{\text{cyclic}}_{2\,5}$ contributes to
$E_{5\,2}$ because the demand must be brought to node $5$ and then it must
later be brought to node $2$. It’s important to understand that once this
demand is dropped off at node 5, it contributes to _direct_ off-board demand
$D^{\text{direct}}_{5\,2}$ as discussed above.

To summarize the flow of demand in this example, we can write the following
table which shows how relevant components of demands are nonzero at various
moments of time:

Component | Description of most recent event.
---|---
$D_{2\,5}^{\text{cyclic}}$ | Initial material is at node 2; must be brought to node 5, then node 2
$E_{5\,2}^{m=1}$ | Box picked up from node 2 by truck 1; must go to node 5, then node 2
$D^{\text{direct}}_{5\,2}$ | Box dropped off and emptied at node 5 by truck 1, must be returned to node 2

At this point, the situation can continue. Suppose that truck 3 now picks up
the empty box. Then, then route for the box would end as follows:

Component | Description of most recent event.
---|---
$E_{2}^{m=3}$ | Empty box picked up from node 5 by truck 3; next stop: node 2
0 | Empty box returned to node 2 by truck 3, requirements fulfilled

Note that our notation may cause confusion initially. When truck #3 picks up
the empty box from node 5, the demand tensor component that gets a
contribution is $E_{2}^{m=3}$ which makes no reference to node 5. This is
because node 5 is no longer relevant. The fact that the node is currently
located at node 5 is handled by tracking truck locations, which is a separate
matter from tracking demand flow.

The general behavior of cyclic and direct demand, at rank 3 and beyond, is
intuitive but even more confusing. The following table shows a sequence of
events for cyclic initial demand starting at node 3 that must go to node 7 and
then node 4 before returning to node 3.

Component | Description of most recent event.
---|---
$D_{3\,7\,4}^{\text{cyclic}}$ | Initial material is at node 3; must be brought to node 7, then node 4, then node 3
$E_{7\,4\,3}^{m=2}$ | Picked up from node 3 by truck 2, next stop node 7
$D_{7\,4\,3}^{\text{direct}}$ | Dropped off at node 7 by truck 2; must be brought to node 4, then node 3
$E_{4\,3}^{m=1}$ | Picked up from node 7 by truck 1, next stop node 4
$D_{4\,3}^{\text{direct}}$ | Dropped off at node 4 by truck 1; must be brought to node 3
$E_{3}^{m=3}$ | Picked up from node 4 by truck 3, next stop node 3
0 | Dropped off at node 3 by truck 3, requirements fulfilled

#### Restricted Driving Windows

Typical VRPs involve minimizing driving time to accomplish the goal of
fulfilling all deliveries. However, in a commercial setting there is a
limitation on the time in which trucks can drive. As a result, we may need to
consider routes that fail to satisfy all demand.

Suppose that all trucks are only allowed to drive during an overall period of
time $T_{\mathrm{max}}>0$. The trucks drive simultaneously during this time.
We are not necessarily guaranteed that it is possible to fully satisfy demand
within that constraint, and the optimization goal is no longer obvious because
we need to make some decision about the relative importance of maximizing
demand satisfied and minimizing driving time.

###  II.3 Aisin Corporation Vehicle Routing Problem

The goal of this work is develop a new technique for solving a supply chain
logistics problem that arises in the operations of Aisin Corporation. In this
section, we explain the remaining complexities of that Aisin Corporation VRP
which we refer to as the AVRP for brevity. Note, however, that we do not
consider AVRP to be a well-defined computational problem; it is better thought
of as a problem instance. In fact, when we discuss the AVRP below, we always
mean a specific instance which has 21 nodes and a specific demand structure
that we now explain.

The general VRP from section II.2 is carefully designed to already accommodate
most of the key details of the AVRP already. As a result, an instance of the
general VRP can be found to model the AVRP. Our approach is therefore to train
a machine learning model (see section III) that can solve the general VRP and
to then apply it to instances that approximate the AVRP.

Perhaps the most substantial AVRP complexity is the presence of individual
boxes. Demand is not an ambiguous real number but is composed of discrete
boxes that occupy a certain volume and have certain routing requirements. We
can use an index $a$ which we call box number:

$a\in\\{1,\ldots,\text{number of boxes}\\}$

to list all of the boxes. Given a box number $a$, there is a specific routing
requirements

$R_{a}=\left(R_{a}^{1},R_{a}^{2},\ldots,R_{a}^{r_{a}}\right)$ (2)

where each $R_{a}^{k}$ is a node. The meaning of this is that box $a$ must
start at the node $R_{a}^{1}$ and then it must visit the node $R_{a}^{2}$ and
so on. Moreover, for the AVRP, after visiting the final node $R_{a}^{r_{a}}$,
_all boxes must then be returned to the starting node_.

The difficulty of the AVRP somewhat reduced by the following facts:

  * •

All boxes either have $r_{a}=2$ or $r_{a}=3$.

  * •

Although there $\sim 330,000$ boxes for the AVRP, there are actually “only”
107 unique paths for boxes.

Figure 2: Depiction of the time matrix for the AVR.P Figure 3: Connectivity
graph for the AVRP of section II.3. Lines indicate pairs of the 21 nodes that
trucks drive between in the routes determined by Aisin Corporation logistics
experts. 142 trucks deliver approximately 340,000 boxes containing $\sim
15,000$ unique parts. Among these parts, there are 107 unique routing
requirements.

Given these observations, a general VRP instance that models the AVRP must
have initial off-board rank-2 and rank-3 cyclic demand and no initial direct
demand. We sometimes refer to the simplification of using continuous
quantities for demand, rather than discrete boxes, as the _box soup
simplification_.

The AVRP has 21 nodes and it has driving time windows: $T_{\mathrm{max}}$ is
equal to 16 hours, providing a pair of 8 hour shifts for each truck. Driving
times between nodes are illustrated in figure 2. The scale of the initial
demand is substantial: Aisin Corporation logistics experts currently use 142
trucks to delivery parts following routes illustrated in figure 3.

##  III Policy Neural Networks

There are a variety of ways to solve routing optimization with reinforcement
learning [6, 7]. Our specific model is an encoder and decoder directly
inspired by that of Kool _et al._ [4]. Their model is quite general: after
training with REINFORCE [8], it performs well for numerous routing problems
including the traveling salesman problem, basic vehicle routing problems, and
the orienteering problem. However, it does not account for multiple trucks.
Moreover, there is no obvious way to incorporate a tensor demand structure
into their model without a substantially new approach.

###  III.1 RL Structure for Routing Problems

Before describing our neural networks, we first explain how a routing problem
like the general VRP fits into the framework of reinforcement learning and
also how and encoder and decoder furnish a policy.

Reinforcement learning concerns a Markov decision process (MDP) where an
agent, presented with _state_ of the _environment_ , performs an _action_ of
its choice which results in a new environment state and gives the agent some
_reward_. The new state as well as the reward are both stochastic: there is a
probability of a given new state and reward value given the original state and
the agent’s action. The goal of the agent is not to maximize the reward for a
given action but to maximize the long term reward (a concept known as the
_return_).

The agent does not know the probability of getting a certain new state and
action, but can learn through experience the best actions to take in given
states. The agent learns a _policy_ which is a probability distribution over
possible actions to take in a given state. In other words, given a state $s$
and a potential action $a$, the agent computes a quantity
$\pi(a\,|\,s)\in[0,1]$ such that $\sum_{a^{\prime}}\pi(a^{\prime}\,|\,s)=1$.
$\pi$, interpreted as a conditional probability distribution, is known as a
policy, and the agent samples from $\pi$ to select an action. Finding the
optimal policy (the one that maximizes the expectation value of return) is the
goal of the agent’s learning process.

Consider the case of a basic vehicle routing problem with one truck. When the
truck is at a given node $\xi_{t-1}$ at time $t-1$, we want to use an RL agent
to determine the next node $\xi_{t}$ for the truck to drive to.

The most obvious approach is to make the state include the following
information:

  * •

The route so far up to a given moment: $(\xi_{0},\xi_{1},\ldots,\xi_{t-1})$,

  * •

The current remaining truck capacity,

  * •

The remaining demand to be picked up at each node,

  * •

The time matrix.444The time matrix is static throughout the episode, but is
conveniently included in the state data as we may want to train over states
with various time matrices.

Given this, the probability of going to node $z$ in a given state can be
written as

$\pi\left(z\,|\,(\xi_{0},\ldots,\xi_{t-1}),D_{t-1}\right).$

where $D_{t-1}$ is meant to include all of the demand information at time
$t-1$.

Assuming that we use the same policy $\pi$ for every step of the route, the
probability for selecting an entire route $x_{0},\ldots,\xi_{k}$ is

$\pi(\xi\,|\,D_{0})=\prod_{t=1}^{k}\pi\left(\xi_{t}\,|\,(\xi_{0},\ldots,\xi_{t-1}),D_{t-1}\right).$
(3)

This formula leads to an important observation that we will make use of when
discussing the learning algorithm below. Rather than thinking of the route as
consisting of $k$ actions, we can alternatively think of it as one single
action which has probability given by equation (3). Although this may seem
unnecessarily complicated, it’s convenient for the REINFORCE algorithm which
involves the logarithm of the probability which conveniently converts to
product in equation (3) to a summation.

#### RL Structure With Multiple Trucks

How does the discussion above need to change when we consider a vehicle
routing problem (or another routing problem) with multiple trucks? There are
two natural approaches:

  * •

Use a different policy for each truck, and have multiple agents interact
simultaneously with the environment, learning to work together.

  * •

Use the same shared policy for each truck.

The first approach is arguably a more powerful technique, allowing different
trucks to use different strategies in the same situation. However, the second
approach is simpler to implement and still has the potential to approach
optimality for vehicle routing problems. We use the second approach throughout
this work.

The concept is that every truck has the same policy and views every other
truck as a part of the environment. At the start of an episode, all trucks are
at initial nodes and we start with the first truck ($m=1$). That truck is
presented with the environment which can include, in principle, all of the
information about the locations of the other trucks as well as all of the
initial demand. The $m=1$ truck uses the (shared) policy to select its next
node. We then go to the next truck $m=2$ and do the same.

After all $N$ trucks have assignments, the next step has an important
difference. All trucks now drive to their selected nodes, but they may not all
arrive at the next node at the same time. This is controlled by a time matrix
$T_{ij}$ giving driving times between nodes. Suppose that truck $m=3$ happens
to arrive at its node first. In that case, we proceed by using the policy for
truck 3 to give it a new node. When we do this, every truck other than truck 3
is treated as a part of the environment. After assigning a new node for truck
3, the environment is updated to the state where whichever next truck arrives
at its destination node at the earliest time.

In this example, we refer to the truck $m=3$ as the _active_ truck while the
other trucks with $m\neq 3$ are called _passive_ trucks. One point of
potential confusion here is that there are two usages of “time”. The first,
which we will sometimes refer to as _physical_ time, is the time measured by
the time matrix. The order in which active trucks are selected is determined
by the order of the physical times for arrivals. The other “time” is a
discrete index which enumerates arrival nodes for trucks. It’s important to
understand that if we say that an episode has a “route”
$(\xi_{0},\ldots,\xi_{k})$, then the nodes $\xi_{t}$ are not all for the same
trucks. We thus need to separately keep track of the active trucks at each
time step $(m_{0},\ldots,m_{k})$.

###  III.2 Encoder Without Tensor Demand

We begin by discussing a modification of the model of Kool _et al._ which
accounts for multiple trucks. This model accounts for many of the complexities
in the problem, but does not have any way to deal with tensor demand structure
described in section II.2. Tensor demand structure requires a modification to
the attention mechanism, and we describe two approaches to this later.

The encoder-decoder model we use follows the basic idea of the transformer
network [9]. A sequence of input data is converted to a sequence of vectors
with dimension $d$ by an encoder. Then, a decoder acts on the encoded sequence
and some additional information (called context) to determine a probability
distribution over the inputs. We can then select one of the inputs by sampling
from that distribution.

#### Encoder Overview

The encoder is essentially identical to the encoder of Kool _et al._ , so we
do not cover it in great detail here. The input data is a sequence of node
coordinates $\mathbf{x}_{1},\ldots,\mathbf{x}_{n}$ with each $\mathbf{x}_{i}$
a two-dimensional point.555We use two dimensions in our analysis, making nodes
points on a plane. However, any dimension can be used as an input dimension.

The input sequence should contain information not only about the locations of
the points but also about the initial demand structure. Initially, even if
there is high-rank tensor demand, we can compute a myopic rank-2 demand
$D_{ij}$ giving the material that is located at node $i$ and needs to go to
node $j$ as its first stop. For example, if we have cyclic rank-3 initial
demand $D^{\mathrm{cyclic}}_{ijk}$, then we can sum over the third index to
obtain a contribution to $D_{ij}$. At this point, define

$\displaystyle\delta^{\mathrm{out,init}}_{i}$ $\displaystyle=\sum_{j}D_{ij},$
(4) $\displaystyle\delta^{\mathrm{in,init}}_{i}$
$\displaystyle=\sum_{j}D_{ji}.$ (5)

These quantities are “myopic outgoing and ingoing demands” for every node. We
can concatenate the initial coordinates with these demands:

$\overline{\mathbf{x}}_{i}=\mathbf{x}_{i}\oplus\left(\delta_{i}^{\text{in,init}},\delta_{i}^{\text{out,init}}\right)$
(6)

where $\oplus$ denotes direct sum (which is equivalent to concatenation in
this context). We use these extended vectors
$(\overline{\mathbf{x}}_{1},\ldots,\overline{\mathbf{x}}_{n})$ as the sequence
of inputs for the encoder.

The first encoding step is a learned linear map with bias from the initial
input space $\mathbf{R}^{4}$ to an encoding space $\mathbf{R}^{4}$. (In our
experiments, we typically take $d=128$.) We denote this by

$\mathbf{h}^{0}_{i}=W^{\mathrm{init}}\overline{\mathbf{x}}_{i}+\mathbf{b}^{\mathrm{init}}$
(7)

where $W^{\mathrm{init}}$ is a $(d,4)$ matrix and $\mathbf{b}^{\mathrm{init}}$
is a $d$-dimensional vector. We emphasize that the same mapping is applied to
every input entry in the sequence: $W^{\mathrm{init}}$ and
$\mathbf{b}^{\mathrm{init}}$ do not depend on $i$.

After this initial encoding, we proceed with a sequence of three encoder
layers. Each encoder layer can be thought of as a two step process: an
attention layer (equation (8)) followed by a feedforward layer (equation (9)).

$\tilde{\mathbf{h}}^{l-1}_{i}=\mathrm{BN}\left(\mathbf{h}^{l-1}_{i}+\mathrm{MHA}\left(\mathbf{h}^{l-1}_{i}\right)\right),$
(8)

$\mathbf{h}^{l}_{i}=\mathrm{BN}\left(\tilde{\mathbf{h}}^{l-1}_{i}+\mathrm{FF}\left(\tilde{\mathbf{h}}^{l-1}_{i}\right)\right).$
(9)

In these equations, $\mathrm{BN}$ is a batch normalization layer [10],
$\mathrm{FF}$ is a feedforward network, and MHA is a multi-head attention
layer which we describe in detail below. The feedforward layers have a single
hidden dimension $d_{\mathrm{ff}}$ and consist of a linear layer with bias
mapping $\mathbf{R}^{d}\to\mathbf{R}^{d_{\mathrm{ff}}}$ followed by a ReLU
activation function, a dropout layer, and finally a linear map with bias back
to $\mathbf{R}^{d}$.

#### Multi-Head Attention

The function MHA is a multi-head attention mechanism identical to that of [4].
Below we consider two major generalizations of this attention mechanism to
deal with tensor demand structure, and this subsection establishes the
groundwork needed for those generalizations.

We begin by using prior embedded nodes
$\mathbf{h}_{1},\ldots,\mathbf{h}_{n}\in\mathbf{R}^{d}$ to compute vectors
known as queries, keys, and values. In a single-head attention mechanism, we
compute a single query, key, and value vector for each encoded node
$\mathbf{h}_{i}$:

$\displaystyle\mathbf{q}_{i}$
$\displaystyle=M^{\mathrm{query}}\,\mathbf{h}_{i}\in\mathbf{R}^{\alpha},$ (10)
$\displaystyle\mathbf{k}_{i}$
$\displaystyle=M^{\mathrm{key}}\,\mathbf{h}_{i}\in\mathbf{R}^{\alpha},$ (11)
$\displaystyle\mathbf{v}_{i}$
$\displaystyle=M^{\mathrm{value}}\,\mathbf{h}_{i}\in\mathbf{R}^{d}.$ (12)

Here, each $M$ is a matrix mapping $\mathbf{R}^{d}$ to either $\mathbf{R}^{d}$
or $\mathbf{R}^{\alpha}$ where $\alpha$ is some a new hyper-parameter.

For the multi-head attention mechanism, we have a positive integer
$n_{\mathrm{heads}}$ which we typically take to be 6. For each
$s\in\\{1,\ldots n_{\mathrm{heads}}\\}$, we have a different query, key, and
value map and thus different queries, keys, and values computed:

$\displaystyle\mathbf{q}_{s\,i}$
$\displaystyle=M_{s}^{\mathrm{query}}\,\mathbf{h}_{i}\in\mathbf{R}^{\alpha},$
(13) $\displaystyle\mathbf{k}_{s\,i}$
$\displaystyle=M_{s}^{\mathrm{key}}\,\mathbf{h}_{i}\in\mathbf{R}^{\alpha},$
(14) $\displaystyle\mathbf{v}_{s\,i}$
$\displaystyle=M_{s}^{\mathrm{value}}\,\mathbf{h}_{i}\in\mathbf{R}^{\beta}.$
(15)

The linear maps $M$ are learned during training. Note that like other aspects
of the encoder that we have discussed, $i$ behaves as batch index, allowing
sequences to have arbitrary length.

The next step is to compute a _compatibility_ for every query-key pair (for
each head). We define

$u_{s\,ia}=\frac{1}{\sqrt{\alpha}}\mathbf{q}_{s\,i}\cdot\mathbf{k}_{s\,a}$
(16)

with $\cdot$ denoting a standard dot product. After this, a softmax version of
compatibility is computed

$\rho_{s\,ia}=\frac{\exp(u_{s\,ia})}{\sum_{b}\exp(u_{s\,ib})}\in\mathbf{R}$
(17)

which is used to weight a sum over values:

$\mathbf{h}_{s\,i}^{\prime}=\sum_{a}\rho_{s\,ia}v_{s\,a}.$ (18)

The only remaining step to to merge the data from the $n_{\mathrm{heads}}$
attention heads. To do this, we simply concatenate the output from each head,

$\mathbf{h}_{1\,i}^{\prime}\oplus\ldots\oplus\mathbf{h}_{n_{\mathrm{heads}}\,i}^{\prime}$

and use a learned linear map with bias on this vector, from dimension
$n_{\mathrm{heads}}\beta$ to dimension $d$ to recover a vector
$\mathbf{h}^{\prime}_{i}\in\mathbf{R}^{d}$.

We use the symbol MHA to denote the function which starts with encoded vectors
$\mathbf{h}_{i}\in\mathbf{R}^{d}$, and returns the output sequence
$\mathbf{h}^{\prime}_{i}\in\mathbf{R}^{d}$. MHA computes queries, keys, and
values following equations (13)-(28), then computes compatibility and new
encoded vectors for each head, and finally maps to the original encoding
dimension.

###  III.3 Decoder Without Tensor Demand

Unlike our discussion of the encoder, this section deviates meaningfully from
the model of [4] because we include new techniques for using multiple trucks.

After encoding, through $l$ layers, we obtain a tuple of $n$ vectors
$\left(\mathbf{h}^{l}_{i}\right)_{i=1}^{n}$ which are interpreted as encoded
nodes for the graph. To obtain the probability of selecting a given node as a
next action, we “decode” the nodes along with some additional information
called context.

At the moment of decoding, we are given

  * •

The encoded nodes $\left(\mathbf{h}^{l}_{i}\right)_{i=1}^{n}$ which were
encoded once at the start of the episode,

  * •

the active truck $m_{t-1}$,

  * •

the current on-board demands $E^{m}_{i_{1},\ldots,i_{r}}$,

  * •

the current off-board demands
$D{i_{1},\ldots,i_{r}},D^{\mathrm{cyclic}}{i_{1},\ldots,i_{r}}$,

  * •

the next expected nodes for each passive truck and the time until those trucks
arrive, and

  * •

the remaining capacities for all of the trucks.

This is an enormous amount of information, and we do not attempt to convey all
of it without loss to our agent.

#### Information Added to Nodes

As a first step, we consider a myopic form of off-board and on-board demand.
We define

$\epsilon^{m}_{i}=\sum_{i_{2},\ldots,i_{r}}E^{m}_{i,i_{2},\ldots,i_{r}}$ (19)

and

$\delta_{i}^{\mathrm{out}}=\sum_{i_{2},\ldots,i_{r}}D^{\mathrm{total}}_{i,i_{2},\ldots,i_{r}},$
(20)

where $D^{\mathrm{total}}$ is the sum of cyclic and direct demand. In words,
$\epsilon^{m}_{i}$ is the total material on truck $m$ which needs to be
dropped off at node $i$ for its next stop, and $\delta_{i}^{\mathrm{out}}$ is
the total material at node $i$ that is waiting to be picked up. We will also
define an ingoing myopic off-board demand

$\delta_{i}^{\mathrm{in}}=\sum_{i_{1},i_{3},\ldots,i_{r}}D^{\mathrm{total}}_{i_{1},i,i_{3},\ldots,i_{r}},$
(21)

but we won’t need it for the time being.

The quantities $\epsilon$ and $\delta$ do not fully encode on-board and off-
board demand but instead only give the most immediately relevant aspects of
the demand structure. Below we will give a technique than can encode the full
tensor structure at the cost of substantial memory consumption.

Now, let $m_{\star}$ be the active truck index. We then modify the encoded
nodes as follows

$\overline{\mathbf{h}}_{i}=\mathbf{h}_{i}\oplus\left(\delta_{i},\epsilon_{i}^{m_{\star}},\epsilon_{i}^{1},\epsilon_{i}^{2},\ldots,\epsilon_{i}^{m_{\star}-1},\epsilon_{i}^{m_{\star}+1},\ldots,\epsilon_{i}^{N}\right)$
(22)

where $\oplus$ is concatenation.

It’s worth stopping to observe some key principles for these new encoded
nodes. First, note that everything on the right hand side of equation (22)
strictly corresponds to the appropriate node: the index $i$ consistently
appears on both sides. This is one of the main reasons that it is difficult to
convey a tensor demand structure with attention models: we tensor demand
involves more than one node at a time. Our usage of myopic demands avoids the
difficulty at the cost of presenting the agent with incomplete environment
information.

Another important principle of equation (22) is the ordering of components.
The original encoded vectors have dimension $d$. After the $d^{\mathrm{th}}$
component, we have a slot for the off-board demand. Then we have a slot for
the on-board _active truck’s_ demand. Finally we have $N-1$ slots for the on-
board demands of passive trucks. Note that very little care is taken with
regard to the order of the passive trucks; this is intentional as all passive
trucks should be treated on equal footing.

#### Additional Contextual Information

There is still additional information that we need to convey: the remaining
truck capacities and the locations of trucks. To do so, we follow the spirit
of [4] and introduce one special _context node_. To define it, let $m_{\star}$
be the active truck index and put

$\mathbf{C}=\left(C_{m_{\star}},C_{1},C_{2},\ldots,C_{m_{\star}-1},C_{m_{\star}+1},\ldots,C_{N}\right)$
(23)

where $C_{k}$ is the capacity remaining for truck $k$. We will use
$\mathbf{C}$ as a part of the context vector, but we need to include also
information about truck locations. Let $z_{1},\ldots,z_{N}$ denote the nodes
of all trucks in the sense that $z_{m_{\star}}$ is the current node of the
active truck from which it is about to depart and, for the passive trucks,
$z_{1},\ldots,z_{m_{\star}-1},z_{m_{\star}+1},\ldots,z_{N}$ are the next
scheduled that the passive trucks are _currently heading toward_. Ideally, we
would like to append to the context node

$\left(h_{m_{\star}},h_{z_{1}},h_{z_{2}},\ldots,h_{z_{m_{\star}-1}},h_{z_{m_{\star}+1}},\ldots,h_{z_{N}}\right)$

but this would be extremely expensive: the context vector would have $dN$
dimensions just from these components. To avoid this, we take the view that
the passive truck is less important than the active truck, and use a single-
layer feedforward neural network $f$, consising of a linear layer, ReLU
nonlinearlity, and then one more linear layer, to reduce the dimension of the
passive trucks. From this we can define

$\mathbf{H}=\left(h_{z_{m_{\star}}},f\left(h_{z_{1}}\right),f\left(h_{z_{2}}\right),\ldots,\right)\\\
\left(f\left(h_{z_{m_{\star}-1}}\right),f\left(h_{z_{m\star+1}}\right),\ldots,f\left(h_{z_{N}}\right)\right).$
(24)

There is one more ingredient for the context node. An important piece of
information is the time until each passive node will arrive at its next
scheduled destination. Let $t_{m}$ denote the time until truck $m$ will arrive
at its next stop. We emphasize that $t_{m}$ measures the remaining physical
time (see section III.1) until the truck arrives. It is not the absolute
physical arrival time of the scheduled event for truck $m$ but rather the
difference between that absolute time and the physical time of the current
event for the current active truck. In particular, note that we can have
$t_{m}=0$ if $m=m_{\star}$ or in the event where truck $m$ has the same
arrival time as the active truck.

Now we define

$\mathbf{T}=\left(t_{1},\ldots
t_{m_{\star}-1},t_{m\star+1},\ldots,t_{N}\right).$ (25)

Note that the last $N-1$ components of $\mathbf{H}$ (equation (24)) correspond
to the same trucks with the same order as the components of $\mathbf{T}$. This
consistency is what matters. With different events, the same components may
correspond to different trucks, but for any given event, the components of
$\mathbf{C},\mathbf{H},$ and $\mathbf{T}$ line up in the same way.

We finally define the _context node_ :

$\mathbf{h}_{\mathrm{ctx}}=\mathbf{H}\oplus\mathbf{T}\oplus\mathbf{C}.$ (26)

#### Decoder Structure

We now take the modified nodes of equation (22) and put them through a single
layer with a structure identical to the encoder layers of equation (8) and (9)
except that the nodes have a greater dimension due to the modifications in
equation (22) and one additional modification explained momentarily. We denote
the output as $\left(\overline{\mathbf{h}}^{1}_{i}\right)_{i=1}^{n}$.

The additional modification is that, following [4], we adjust the computation
of keys and values in equations (14) and (15) by adding _source terms_ :

$\displaystyle k_{s\,i}$
$\displaystyle=M_{s}^{\mathrm{key}}\,\mathbf{h}_{i}+\mathbf{u}_{s}^{\mathrm{key,out}}\,\delta_{i}^{\mathrm{out}}+\mathbf{u}_{s}^{\mathrm{key,in}}\,\delta_{i}^{\mathrm{in}},$
(27) $\displaystyle v_{s\,i}$
$\displaystyle=M_{s}^{\mathrm{value}}\,\mathbf{h}_{i}+\mathbf{u}_{s}^{\mathrm{val,out}}\,\delta_{i}^{\mathrm{out}}+\mathbf{u}_{s}^{\mathrm{val,in}}\,\delta_{i}^{\mathrm{in}}.$
(28)

Here, $s$ is an index for attention heads, and various $\mathbf{u}_{s}$ are
learned vectors with the same dimension as the left hand side of the equations
they appear in; for example, $\mathbf{u}_{s}^{\mathrm{key,out}}$ is a vector
with the same dimension as keys which is $\alpha$ as specified in equation
(14). Note $\delta_{i}^{\mathrm{out}}$, defined in equation (20), is a real
number that re-scales the vector $\mathbf{u}_{s}^{\mathrm{key,out}}$. This
modification of keys and values helps to convey the current demand situation
to the attention mechanism directly.

We now proceed with a second attention layer, this one with the same number of
heads $n_{\mathrm{heads}}$ but defined on $n+1$ nodes: the $n$ nodes
$\left(\overline{\mathbf{h}}^{1}_{i}\right)_{i=1}^{n}$ from the first decoder
layer, and the one context node 26. However, for this attention layer,
following [4], we only make a single query from the context node and have keys
for all of the other nodes. In other words, for each head we compute one query
(for the context node), $n$ keys, and $n$ values (for the other nodes). In
equations (16)-(18), the index $i$ only take on a single value. We use sources
$\delta_{i}^{\mathrm{out}},\delta_{i}^{\mathrm{in}}$ just as in equations (27)
and (28). Moreover, for this layer we only compute MHA as described at the end
of section III.2. This is a pure attention layer (as opposed to and encoder
layer which uses equation (8) and (9).

The output of this second layer is one new context vector
$\mathbf{h}_{\mathrm{ctx}}^{\prime}$ with dimension $d_{\mathrm{ctx}}$. This
vector is then used for a final (third) layer much like the second layer
although we only use one head. Once again, a query $q_{\mathrm{ctx}}$ is
computed only for $\mathbf{h}_{\mathrm{ctx}}^{\prime}$ and keys are computed
for the encoded nodes $\overline{\mathbf{h}}^{1}_{i}$.

For this last layer, we obtain compatibility in the usual way except that we
regulate with $\tanh$ and we allow for _masking_ :

$u_{i}=\begin{cases}A\tanh(q_{\text{ctx}}\cdot k_{i})&\text{if node $i$ is
allowed}\\\ -\infty&\text{otherwise}\end{cases}$ (29)

where $A$ is a hyper parameter that we take to be 10. The idea is that we can
block certain nodes for the active truck to drive to if we know, for some
reason, that doing so is a poor choice. We describe the specific rules we use
for masking in section [[FILL]].

Finally, the $u_{i}$ are converted to probabilities with a softmax layer, and
these probabilities are interpreted as the values of the policy: the
probabilities of selecting node $i$ for the active truck’s next destination:

$\pi(i)=\frac{e^{u_{i}}}{\sum_{j=1}^{n}e^{u_{j}}}.$ (30)

There is no need for values to be computed in the final attention layer.

###  III.4 Incorporating Tensor Demand Structure

In the prior sections, we have not fully incorporated tensor demand structure
described in section II.2. We have been able to incorporate aspects of the
demand structure by reducing to quantities like $\delta^{\mathrm{out,in}}$ and
$\epsilon^{m}_{i}$; these quantities fit into the framework of [4] because
they can be associated with a single node. Consider for example equation (22)
where we append the encoded nodes. The left and right hand sides of equation
(22) have the same $i$ index in a consistent manner. A similar observation can
be made for equations (27) and (28).

The fact that a quantity like a demand matrix $D_{ij}$ cannot be conveyed to
an encoder or decoder demonstrates a limitation of the attention model of [4].
To be certain, their model is very general and very powerful, providing
excellent solutions to a wide range of combinatorial optimization problems.
However, the difficulty arises in optimization problems where the problem
structure unavoidably involves data related to subsets of nodes.

As a example of a combinatorial optimization problem beyond the scope of [4],
we could consider a variant of the traveling salesman problem where we are
given a tensor $R_{ijk}$ and the goal is to navigate through the graph such
that we collect a reward $R_{ijk}$ when the agent moves from node $i$ to node
$j$ and next to node $k$. If the goal is to find the tour that maximizes the
sum of these rewards, or perhaps to find the path that does so within a time
constraint (given travel times between nodes), then there is no way around the
fact that a rank 3 tensor is central to the problem. This is a situation where
the attention model of [4] would require a meaningful modification.

In this section, we describe two different modifications of [4] which
incorporate tensor demand structure. The first, _dynamical masking_ , is a
fairly simple modification that does not result in a substantial computational
overhead. However, it only accounts for rank-2 quantities. The second
technique, which we refer to as a _tensor attention mechanism_ , is general
and powerful but can be extremely memory consuming.

#### Dyamical Masking

The step of the attention mechanism that involves more than one node is the
dot product evaluation between keys and queries. If we want incorporate a
demand tensor $D_{ij}$, a natural idea would be to replace the dot product
with

$\frac{1}{\sqrt{\alpha}}G_{ij}\,\mathbf{q}_{i}\cdot\mathbf{k}_{j}$ (31)

where $G$ is some tensor determined by $D$. This approach can exaggerate
query-key compatibility in cases where $D_{ij}$ is large and suppress
compatibility when the demand is small.

There are a few reasonable choices for $G$. The first is $G_{ij}=1$ which
reduces to a basic dot product compatibility. Next is $G_{ij}=M_{ij}$ where
$M$ is the mask defined as $M_{ij}=1$ when $D_{ij}>0$ and $M_{ij}=-\infty$
otherwise. Both of these are within the methodology of [4]. A third and more
novel choice of $G$ is $G_{ij}=\log D_{ij}$. This last form has several
virtues: it reduces to a mask in the case in the sense that it approaches
$-\infty$ as $D{ij}\to 0+$. Moreover, it can exaggerate compatibility when
$D_{ij}$ is large. A simple additional adjustment is to use

$G_{ij}=AD_{ij}+B\log D_{ij}$

which is more sensitive to changes in $D_{ij}$ for larger values.

Rather than having to pick from these various choices, we can in fact choose
all of them by taking advantage of the multiple heads. In other words, for a
given head $s\in\\{1,\ldots,n_{\mathrm{heads}}\\}$, we can put

$G^{s}_{ij}=A^{s}_{\mathrm{basic}}+A^{s}_{\mathrm{mask}}M_{ij}+A^{s}_{\mathrm{log}}\log
D_{ij}+A^{s}_{\mathrm{lin}}D_{ij}.$ (32)

In principle, even more terms can be used, and a more thorough investigation
of various models would be sensible.

#### Tensor Attention Mechanism

The drawback of dynamical masking is that it specializes to rank 2 tensors. To
move to arbitrary rank, we could add terms that sum over certain indices like
$\sum_{k}D_{ijk}$ but this will not access to full structure of the tensor.

There is, however, a way to modify the attention mechanism at a more
fundamental level. In equation (14)-(15), we obtain queries, keys, and values
by mapping embedded nodes $\mathrm{h}_{i}$ to keys by means of “attention
vector maps” $M^{\mathrm{query,key,value}}$. These maps create a
correspondence: for each node there is a query and so on. Demand structure can
then be presented to the decoder through equations (27) and (28). However, we
would like to modify, e.g., equation (27) to get something like

$\mathbf{k}_{i}\overset{??}{=}M^{\mathrm{key}}\mathbf{h}_{i}+\mathbf{u}D_{ijk}.$

This equation is intentionally nonsensical, but it does reveal what we need.
The indices $ijk$ must match on both sides. Thus, in the rank 3 case, rather
than requiring that a single node corresponds to a key, _we instead define a
key $K_{ijk}$ for each 3-tuple of nodes $(i,j,k)$_. We do this as follows:

$K_{ijk}=M^{\mathrm{key}}\left(\mathbf{h}_{i}\oplus\mathbf{h}_{j}\oplus\mathbf{h}_{k}\right)+\mathbf{u}^{\mathrm{key}}D_{ijk}$
(33)

where $M^{\mathrm{key}}$ is a learned linear map (without bias) from
$\mathbf{R}^{3d}$ to $\mathbf{R}^{\alpha}$ and $\mathbf{u}^{\mathrm{key}}$ is
a learned vector with dimension $\alpha$. As before, $\oplus$ denotes
concatenation or, equivalently, direct sum.

Note that $M^{\mathrm{key}}$ acts on the full vector
$\mathbf{h}_{i}\oplus\mathbf{h}_{j}\oplus\mathbf{h}_{k}$. The operation that
maps $(\mathbf{h}_{i})_{i=1}^{n}$ to the the 3-index object
$\left(\mathbf{h}^{\oplus 3}\right)_{i,j,k=1}^{n}$ is just a reorganization,
but it is, unfortunately, an expensive one. In practice, an implementation of
this object would have $b\cdot n^{3}\cdot 3d$ components where $n$ and $d$
are, the number of nodes and the encoding dimension, and $b$ is whatever batch
size is used in the implementation (for, e.g., parallelization). The problem
is the $n^{3}$ factor, which leads to a substantial memory cost for this
technique as the number of nodes grows.

Equation (33) is generalized as follows

$\displaystyle K^{s}_{a_{1}\ldots a_{r}}$
$\displaystyle=M_{s}^{\mathrm{key}}\left(\mathbf{h}_{a_{1}}\oplus\ldots\mathbf{h}_{a_{r}}\right)+\mathbf{u}^{\mathrm{key}}_{s}D_{a_{1}\ldots
a_{r}},$ (34) $\displaystyle V^{s}_{a_{1}\ldots a_{r}}$
$\displaystyle=M_{s}^{\mathrm{value}}\left(\mathbf{h}_{a_{1}}\oplus\ldots\mathbf{h}_{a_{r}}\right)+\mathbf{u}^{\mathrm{value}}_{s}D_{a_{1}\ldots
a_{r}}.$ (35)

In these equations, we refer to the tensor $D_{a_{1}\ldots a_{r}}$ as a
_source_. We can generalize to multiple sources in the obvious way: replacing
$\mathbf{u}_{s}D_{a_{1}\ldots a_{r}}$ by

$\sum_{k=1}^{n_{\mathrm{sources}}}\mathbf{u}_{k,s}\,D^{(k)}_{a_{1}\ldots
a_{r}}.$ (36)

Note that we are not constructing a tensor query. Our method is to keep using
equation 13 for the construction of queries. The concept is that each node
queries a sequence of $r$ other nodes, yielding a compatibility

$u^{s}_{i,a_{1}\ldots a_{r}}=q^{s}_{i}\cdot K^{s}_{a_{1}\ldots a_{r}}$ (37)

from which we find attention weights

$\rho^{s}_{i,a_{1}\ldots a_{r}}=\frac{\exp(u^{s}_{ia_{1}\ldots
a_{r}})}{\sum_{b_{1}\ldots b_{r}}\exp(u^{s}_{ib_{1}\ldots b_{r}})}$ (38)

and finally we obtain new nodes through a value sum:

$h_{i,s}^{\prime}=\sum_{a_{1}\ldots a_{r}}\rho^{s}_{ia_{1}\ldots
a_{r}}V^{s}_{a_{1}\ldots a_{r}}.$ (39)

As before, a final feedforward layer must be used to convert the concatenated
outputs for each head to a single new output node $h_{i}^{\prime}$.

##  IV Training Methodology

Figure 4: Example of a training curve showing the objective function (equation
40) during training.

In this section, we go into some detail for our training techniques. One
aspect of this is our reinforcement learning algorithm which, keeping in line
with [4], is a variant of REINFORCE [8]. This section also elaborates on our
methodology for environment simulation and generation.

#### Objective Function

Reinforcement learning requires a reward definition. For our purposes, the
entire route can be regarded as a single action, and thus we only need to
define a reward $R(\xi)$ for a full route $\xi$. Equivalently, we an define an
objective function $F(\xi)=-R(\xi)$. This approach is natural because of our
use of REINFORCE.

Typical vehicle routing problems can use total driving time as an objective
function to minimize. However, our routing problem has a time constraint
$T_{\mathrm{max}}$ and we are not guaranteed that all demand will be
fulfilled. To address this, we define _demand coverage_ as the percentage
$\eta$ of initial demand that is eventually fulfilled. This quantity requires
care to calculate: when a truck arrives at a node $i$, all rank 1 on-board
demand with index $i$ is dropped off as a final stop. We can keep track of the
accumulated total of such demand as it is dropped off. This total, divided by
the sum of all components of initial demand, is the demand coverage $\eta$.

We also use a parameter $T$ to denote the physical time of the last truck when
it finishes its route. It’s very important to note that $T$ is not the average
time for all trucks.

We then introduce the objective function

$F(\xi)=-B_{\mathrm{coverage}}\eta+T/T_{\mathrm{max}}$ (40)

where $B_{\mathrm{coverage}}$ is a hyperparameter. Note that we are writing
$\xi$ is the input to $F$ to emphasize that $\eta$ and $T$ are determined by
the route (and also initial demand, time matrix, etc.)

$B$ is meant to be greater than 1, and a typical value is 10. The idea is that
demand coverage takes first priority, and until coverage approaches its
maximum value of 1, we do not try to reduce $T$ below the terminal time limit.

#### Environment Simulation

Training the model of section III for the general VRP requires a simulation of
the environment that is able to take advantage of GPU parallelization. We
developed such a simulation using PyTorch. There are several challenges that
our simulation overcomes that we highlight in this section.

Consider multiple episodes for vehicle routing problems which run in parallel.
The truck routes can be stored as a tensor $\xi_{b,t}$. Here, $b$ is a batch
index and $t$ is a time index. The value of $\xi_{b,t}$ is a node providing
the departure node at (indexed, not physical) time $t$ for batch entry $b$.
However, if there are multiple trucks, then it’s not clear which truck
$\xi_{b,t}$ refers to. Thus, we need to track a separate tensor $A_{b,t}$
which specifies which truck is the active truck at time $t$ for batch entry
$b$. This approach allows us to perform operations in parallel over a batch
with a CUDA implementation.

One of the pitfalls of this organizational approach is that routes are likely
to terminate for different batch entries with different $t$. As a result, we
must accept that $\xi_{b,t}$ will have a tail of repeating entries for most
values of $b$.

Demand structure must be tracked with great care for the general VRP. We use
tensors to separately track each rank of on-board demand, cyclic off-board
demand, and direct off-board demand. For example, we use a tensor
$E_{b,m,ijk}$ to track rank-3 on-board demand. The indices refer to,
respectively, the batch entry, the truck number, and the three tensor indices.

#### Environment Generation

Generating episodes is particularly challenging because of the need to
efficiently create examples of demand structures. Episodes start with zero on-
board demand and zero direct off-board demand, but have initial cyclic off-
board demand with ranks 2 and 3. Not just any tensor
$D^{\mathrm{cyclic}}_{ij},D^{\mathrm{cyclic}}_{ijk}$ are acceptable. For
example, a component like $D^{\mathrm{cyclic}}_{232}$ must be excluded. To
create instances, we start with a mask tensor with components which are 1 only
for allowed tensor components. We give random values within an allowed range
for tensors, mask away components that are not allowed. We then randomly
further mask components with some given probability. This is meant to cause
instances to be more representative of real data, where we don’t have all-to-
all connectivity.

#### REINFORCE Implementation

Following [4] we implemented a variant of REINFORCE [8].

The REINFORCE algorithm is a policy-gradient reinforcement learning algorithm.
While many RL algorithms are based on the idea of first trying to estimate
(from experience) the “value” of various actions in a given state, and then
taking actions with higher estimated value, policy-gradient algorithms
circumvent the intermediate step of estimating values. Instead, we work
directly with a parameterized policy, varying parameters to optimize the
return from an episode.

The REINFORCE algorithm, following [11], is given as follows [H] REINFORCE

Inputs:

Parameterized policy $\pi$

Initial parameter $\theta$

while desired performance not achieved do

Using $\pi(\theta)$, generate episode

$(s_{0},a_{0},r_{1},\ldots,r_{T})\leftarrow$ episode

for $t=0,1,2,\ldots,T-1$ do

$G\leftarrow r_{t+1}+\gamma r_{t+2}+\ldots\gamma^{T-t-1}r_{T}$

$\nabla
J\leftarrow\gamma^{t}G\,\nabla_{\theta}\log\left(\pi(a_{t}\,|\,s_{t},\theta)\right)$

$\theta\leftarrow\text{Ascent}(\theta,\nabla J)$

end for

end while

In this algorithm, $\gamma\in(0,1)$ is a fixed discount factor. “Ascent”
refers to any gradient-based ascent optimization step. This could be gradient
ascent on $J(\theta)$ or it could be replaced by other optimization algorithms
like Adam[12].

REINFORCE can learn much faster when a _baseline_ is added. This essentially
means that some function $b$ of states (but not of actions) is constructed
with each episode and the return $G$ in the algorithm is replaced by $G-b(s)$.
This algorithm still converges to the optimal policy theoretically and, with a
well-chosen baseline, does so much faster. This is easiest to understand when
$b(s)$ is taken to be an estimate of the return after state $s$ based on data
from recent previous episodes. In this case, $G-b(s)$ being positive indicates
that this episode was better than expected and thus it’s sensible to increase
the probability of following this sequence of actions. Meanwhile, if $G-b(s)$
is negative, the return is less than what is considered a reasonable par, and
the gradient ascent would reverse and reduce the probability of taking these
actions. The REINFORCE algorithm works regardless of whether or not such a
baseline is used, but the learning time is dramatically reduced with a good
baseline.

For our purposes we take a variant of REINFORCE adapted to our vehicle routing
problem as follows. First, the for the purposes of the algorithm we take the
entire episode to be defined by a single action. In other words, the episode
is just $a_{0},r_{1}$. The action $a_{0}$ is the entire route specification
$a_{0}=(\xi_{1},\xi_{2},\ldots\xi_{k})$ where each $\xi_{i}$ are nodes. This
odd-sounding choice is sensible because with the structure of 3 which makes
the logarithm of the policy equal to a sum over logarithms of probabilities of
each action in an episode. The reward $r_{1}$ is simply the negation of the
route length (or time) $-L(\xi)$ which is computed by summing the appropriate
distances between nodes based on a metric or on known travel times.

The second important aspect of our variant is the baseline methodology. This
idea is roughly adapted directly from [4]. We maintain a “baseline agent”
which uses the same parameterized policy but does constantly update its
parameter $\theta$. Instead, the baseline agent uses an outdated parameter
$\theta_{\text{BL}}$ which is occasionally updated to match the primary
agent’s $\theta$, but only when the agent substantially and consistently
outperforms the baseline.

Our REINFORCE variant is given in algorithm IV. Note that this algorithm is
broken up into epochs and batches.

REINFORCE variant for VRP

Input: Parameterized policy $\pi$

Input: Integers num_epochs, batch_size, batches_per_epoch

Input: Initial parameter $\theta$

$\theta_{\text{BL}}\leftarrow\theta$

for $e=1,\ldots,$ num_epochs do

for $b=1,\ldots,$ batches_per_epoch do

$\xi\leftarrow$ (batch_size many episodes from $\pi(\theta)$)

$\xi_{\text{BL}}\leftarrow$ (batch_size many episodes from
$\pi(\theta_{\text{BL}})$)

$\nabla
J\leftarrow\texttt{batch\\_mean}\left((L(\xi)-L(\xi_{\text{BL}})\nabla_{\theta}\log\left(\sum_{i=1}^{k}\pi(\xi^{i},\theta)\right)\right)$

$\theta\leftarrow\textrm{descent}(\theta,\nabla J(\theta))$

end for

if baseline_test() then

$\theta_{\text{BL}}\leftarrow\theta$

end if

end for

One confusing part of this algorithm may be the summation
$\sum_{i=1}^{k}\pi(\xi^{i},\theta)$. To clarify, this is a sum over the
probabilities computed by the encoder/decoder network at each stage of the
route. $k$ refers to the number of steps in the route and the index $i$ runs
over steps in the route, not over batch entries. The entire computation is
performed for each batch entry and averaged over.

The baseline_test() subroutine returns true when the policy $\pi(\theta)$
substantially outperformed the baseline policy $\pi(\theta_{\text{BL}})$ in
recent episodes. More specifically, after each epoch we compute percentage of
epochs in which the policy outperforms the baseline policy. If this percentage
exceeds 50% for 10 _consecutive epochs_ then we update the baseline
parameters. Moreover, if the percentage exceeds 70% for any epoch, we update
the parameters. There is certainly room for experimentation with different
methods here (like the one-sided T Test used in [4] but our methods were
satisfactory).

##  V Supply Chain Management Workflow

The ultimate goal of our work is to find a way to apply reinforcement learning
techniques for combinatorial optimization problems in a realistic commercially
valuable setting. Training an agent through the methods of sections III and IV
yields approximate solutions to the general VRP described in section II.2.
This section explains how we can use such a trained agent to obtain
approximate solutions to the full AVRP of section II.3.

There are two difficulties to overcome:

  1. 1.

The scale of the AVRP is too large, with 21 nodes and with so much demand that
$\sim 150$ trucks may be necessary to fulfill requirements in the 16 hour time
window.

  2. 2.

The general VRP lacks the discrete box structure of the full VRP.

To deal with the first difficulty, we decompose the graph into pieces that can
be treated by agents trained for a smaller number of trucks and nodes as
described in section V.1. The second difficulty is handled by processing truck
routes obtained through the general VRP into a full-scale simulation of the
AVRP (see section V.2).

###  V.1 Node Subset Search

Consider an instance of the general VRP with $n$ and demand structure
$D^{\mathrm{init}}$. Given the demand structure, the time matrix, and the
driving window $T_{\mathrm{max}}$, we can estimate the number of trucks $N$
that will be necessary to fulfill all requirements.

Suppose that we have an algorithm to find solutions to general VRPs with a
smaller number of nodes and trucks and with smaller demand structure. Our
algorithm works for $n^{\prime}<n$ nodes and $N^{\prime}<N$ trucks.

This situation arises in our context naturally: we can train, for instance, an
agent to solve general VRP instances with 10 nodes and three trucks, a scale
smaller than the AVRP with its 21 nodes and over 100 trucks.

We should be able to use our smaller-scale algorithm to solve the larger
problem by applying it repeatedly to different subsets to nodes to gradually
fulfill all demand requirements. This raises a question of how to find good
subsets.

We begin by looking at the demand structure $D^{\mathrm{init}}$. For
simplicity, assume that this consists only of rank-3 cyclic demand (other
cases are very similar and we describe the necessarily modifications below).
From $D^{\mathrm{init}}$ we can identify the nonzero components. These are
tuples of nodes

$\displaystyle i_{1},$ $\displaystyle j_{1},k_{1}$ $\displaystyle i_{2},$
$\displaystyle j_{2},k_{2}$ $\displaystyle\vdots$ $\displaystyle i_{u},$
$\displaystyle j_{u},k_{u}$

where $u$ is some integer (which happens to be 107 for the AVRP). We can begin
our node search by uniformly randomly selecting one of these triples of nodes
from the list. (In cases where demand also includes rank 2 or another rank, we
include tuples of appropriate length in the list for nonzero demand cases and
we allow such tuples to be selected as well.) After drawing a tuple from the
list, we remove it from the list. Suppose that we select the tuple
$(i_{3},j_{3},k_{3})$. We define a starting subset of nodes as
$A=\\{i_{3},j_{3},k_{3}\\}$ If $3<n^{\prime}$, we continue to draw nodes.
Suppose that we next draw $(i_{5},j_{5},k_{5})$. We now consider the set
$A=\\{i_{3},j_{3},k_{3},i_{5},j_{5},k_{5}\\}$. If any node repeats (for
instance, if $i_{3}=j_{5}$), that entry is only counted once in the set. There
will now be between 4 and 6 elements in $A$. If $|A|<n^{\prime}$, we continue
and otherwise we stop. Continuing in this way, we can either eventually run
out of tuples or we can reach $|A|\geq n^{\prime}$. If we reach
$|A|=n^{\prime}$, we stop and use $A$ as our first guess of a node subset. If
$|A|$ exceeds $n^{\prime}$, we remove the most recently added subset. If we
run out of tuples, we stop.

After this process, we might have $|A|<n^{\prime}$. In this case, we simply
randomly add additional nodes outside of $|A|$ until reaching
$|A|=n^{\prime}$.

At this point, we have obtained a random node subset $A$. We repeat this
process $K$ times to obtain $k_{\text{node draws}}$ different random subsets,
and we apply our algorithm $k_{\text{subset attempts}}$ times for each of the
$k_{\text{node draws}}$ subsets. We compute the mean demand fulfilled for the
$k_{\text{subset attempts}}$ trials, and we select the node subset with the
highest mean demand coverage.

###  V.2 Execution Loop

With a technique for selecting node subsets, we are now in a position to
describe the execution procedure. This begins with the initial demand
structure $D^{\mathrm{init}}$ which is determined by the AVRP’s requirements.
Next, a node subset is selected through the node search technique of section
V.1. We identify the portion of $D^{\mathrm{init}}$ that is supported by the
subset and we map it onto a demand structure $D^{\prime}$ for $n^{\prime}$
nodes. To regulate the policy input, we clip $D^{\prime}$ at some maximum
value $C$. We then apply the trained agent $k_{\text{execution trials}}$ times
and select the trial with the highest percentage of covered demand. This trial
has a specific routing for $N^{\prime}$ trucks and corresponds to a certain
demand fulfillment. The route as well as the on-board and off-board demand at
each step is saved and the initial demand $D^{\mathrm{init}}$ is modified: it
is reduced by the amount of demand satisfied by the route.

This process is repeated, each time first performing node selection and then
finding the best route out of $k_{\text{execution trials}}$ attempts. We
repeat until all demand is satisfied. The total number of iterations of this
procedure multiplied by $N^{\prime}$ will be the total number of trucks needed
for our solution.

###  V.3 Full Scale Simulation

The result of the execution loop yields approximate solutions to the general
VRP. We obtain a collection of routes for various trucks $x_{m\,\tau}$ where
$m$ ranges over trucks and $\tau$ over time steps for each truck.666Here, we
are breaking out earlier convention and using a unified time index $t$ and
instead using $\tau$ to range over the time steps for individual trucks.
However, we still need a way to convert such routes to candidate solutions to
the AVRP of section II.3.

Our strategy is to interpret the routes $x$ as “suggested routes” and to
attempt to use them in a _full-scale_ supply chain simulation. We make use of
a modified variant of the simulation of [13]. Every box is individually
tracked and has rank-2 or rank-3 requirements. Unlike [13], we require that
demand is cyclic: boxes must be returned to their origin node. Each box has a
specific individual volume. The simulation is designed to be as similar as
possible to the actual commercial routing problem of Aisin Corporation.

Trucks follow along the routes $x_{m,\tau}$ that they are assigned from the
execution algorithm and they pick up boxes as is appropriate for their route.
Boxes a picked up according to the algorithm described in [13] and we
carefully ensure that trucks only drive within the allowed drive time windows
(two 8 hour shifts). The result of full-scale simulation is that, rather than
having a list of suggested truck routes, we obtain a precise statement about
what each truck in the supply chain is doing at all times, including exactly
which boxes must be picked up and dropped off at various nodes.

##  VI Results

###  VI.1 Training Parameters

When training the general VRP agent, we used and encoding dimension $d=128$
and three encoder layers and 8 attention heads for all layers except for the
final policy output layer. For feedforward layers we used 64 dimensional
hidden layers. We used dynamical masking as described in section II.2 as we
found that the memory limitations were too prohibitive for full tensor demand
structure. For dynamical masking in the decoder, we used one source $D_{ij}$
given by

$D_{ij}=\sum_{k}D^{\mathrm{total}}_{ijk}+D^{\mathrm{total}}_{ij}$

where $D^{\mathrm{total}}$ is the sum of cyclic and direct off-board demand.
We also used dynamical masking in the first encoding layer with the same
$D_{ij}$ (although for the encoder we are using initial demand while for the
decoder we are using the demand at the moment of decoding).

Training was conducted in batches of length 256 with the Adam optimization
method. Using an initial learning rate of $2^{-23}$, we trained 100 epochs
each consisting of 64 batches each. The learning rate was taken to decay by a
factor of .965 for each epoch until reaching a final rate of $2^{-15}$ at
which point it was held constant. An example training curve is shown in figure
4.

###  VI.2 Execution Performance

Figure 5: Typical demand satisfied by trucks as we assign trucks. Unlike the
algorithm used in [13], we maintain strong demand coverage consistently as we
add more trucks. However, the newly implemented box-return constraint cancels
this benefit. Figure 6: Remaining demand as we iterate through trucks. This is
the remaining demand, not the demand share on individual trucks. Figure 7: The
truck-routing connectivity graph obtained by assigning teams of 3 trucks using
the methods of section V. Note that this figure only shows connectivity
without regard for the demand flow along each edge, routing orientations, or
specific timing details.

The methods described in section V were used with truck groups of size
$N^{\prime}=3$. The estimated demand satisfied by each truck during this
process is shown in figure 5 and the estimated remaining demand as truck
groups are iteratively assigned is shown in figure 6. Upon full-scale
simulation (section V.3), we obtain the the routing graph shown in figure 7.

##  VII Conclusion

While there is much additional work to do in exploring algorithmic and
workflow improvements, these first results demonstrate that this general VRP
agent can successfully train a model to solve the logistics problem. This is
especially noteworthy in that the general VRP agent addresses multiple trucks
and a distributed network of pickup and delivery nodes beyond the spoke and
hub model. This generality extends beyond the needs of the AVRP and can
address a wide variety of logistics situations.

This reinforcement learning approach is computationally demanding, especially
considering multiple trucks and the tensor demand structure, but the
introduction of attention head mechanism and decomposing the agents into sub-
teams of truck reduced the computational burden while still achieving
solutions. The box return constraint especially added to the computational
burden of finding solutions, just as it adds greater complexity to real-life
operations. This suggests that the design of future logistics approaches might
try to mitigate or replace the box return requirement with a different
approach that would increase efficiency and reduce cost.

We were only able to study a few training approaches during the course of this
project. Further work in alternative training approaches would likely find
more efficient and more effective training approaches. While the model
incorporates many key features of Aisin data, the overall workflow was not
optimized for Aisin data. So exploring problem structure unique to the Aisin
data might yield better training results.

And finally, the use of teams of trucks was necessary to make the problem
computationally tractable, and was also successful in yielding solutions, but
we have only explored a small sub-space of how teams of trucks can be used
iteratively to decompose the actions of the entire fleet of trucks. So more
work in this area would likely improve results.

Overall the results are quite promising using classical computing today and
amenable to benefit from quantum computing in the future. And given the
multiple parts of the training algorithm, exploring how to better implement
each part in future studies could yield significant improvement in the overall
solution quality for supply chain logistics.

## References

  * Dantzig and Ramser [1959] George B Dantzig and John H Ramser.  The truck dispatching problem.  _Management science_ , 6(1):80–91, 1959.
  * Toth and Vigo [2002] Paolo Toth and Daniele Vigo.  _The vehicle routing problem_.  SIAM, 2002.
  * Bello et al. [2016] Irwan Bello, Hieu Pham, Quoc V Le, Mohammad Norouzi, and Samy Bengio.  Neural combinatorial optimization with reinforcement learning.  _arXiv preprint arXiv:1611.09940_ , 2016.
  * Kool et al. [2018] Wouter Kool, Herke Van Hoof, and Max Welling.  Attention, learn to solve routing problems!  _arXiv preprint arXiv:1803.08475_ , 2018.
  * Silver et al. [2017] David Silver, Julian Schrittwieser, Karen Simonyan, Ioannis Antonoglou, Aja Huang, Arthur Guez, Thomas Hubert, Lucas Baker, Matthew Lai, Adrian Bolton, et al.  Mastering the game of go without human knowledge.  _nature_ , 550(7676):354–359, 2017.
  * Mazyavkina et al. [2020] Nina Mazyavkina, Sergei Sviridov, Sergei Ivanov, and Evgeny Burnaev.  Reinforcement learning for combinatorial optimization: A survey.  _CoRR_ , abs/2003.03600, 2020.  URL https://arxiv.org/abs/2003.03600.
  * Vinyals et al. [2015] Oriol Vinyals, Meire Fortunato, and Navdeep Jaitly.  Pointer networks.  In C. Cortes, N. Lawrence, D. Lee, M. Sugiyama, and R. Garnett, editors, _Advances in Neural Information Processing Systems_ , volume 28. Curran Associates, Inc., 2015.  URL https://proceedings.neurips.cc/paper/2015/file/29921001f2f04bd3baee84a12e98098f-Paper.pdf.
  * Williams [1992] Ronald J. Williams.  Simple statistical gradient-following algorithms for connectionist reinforcement learning.  _Machine Learning_ , 8(3):229–256, 1992.  doi: 10.1007/BF00992696.  URL https://doi.org/10.1007/BF00992696.
  * Vaswani et al. [2017] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Łukasz Kaiser, and Illia Polosukhin.  Attention is all you need.  _Advances in neural information processing systems_ , 30, 2017.
  * Ioffe and Szegedy [2015] Sergey Ioffe and Christian Szegedy.  Batch normalization: Accelerating deep network training by reducing internal covariate shift.  In _International conference on machine learning_ , pages 448–456. PMLR, 2015.
  * Sutton and Barto [2018] Richard S. Sutton and Andrew G. Barto.  _Reinforcement Learning: An Introduction_.  The MIT Press, second edition, 2018.  URL http://incompleteideas.net/book/the-book-2nd.html.
  * Kingma and Ba [2015] Diederik P. Kingma and Jimmy Ba.  Adam: A method for stochastic optimization.  In Yoshua Bengio and Yann LeCun, editors, _3rd International Conference on Learning Representations, ICLR 2015, San Diego, CA, USA, May 7-9, 2015, Conference Track Proceedings_ , 2015.  URL http://arxiv.org/abs/1412.6980.
  * [13] To appear: Toward supply chain logistics with quantum optimization algorithms.