Optimal management of an AGV based internal distribution
system: MILP formulation and heuristic approach
M. Bocciaa , A. Mancusoa , A. Masonea , A. Sforzaa and C. Sterlea,∗a Department of Electrical Engineering and Information Technology,

University Federico II of Naples, Naples, Italy{maurizio.boccia, andrea.mancuso, adriano.masone, antonio.sforza, claudio.sterle}@unina.it,∗ Corresponding author
Extended abstract submitted for presentation at the 11th Triennial Symposium on
Transportation Analysis conference (TRISTAN XI)
June 19-25, 2022, Mauritius Island

March 31, 2022
Keywords: AGV transportation system; battery constraints; scheduling; MILP; heuristic

1

Introduction

Automated guided vehicles (AGVs) are driverless transportation systems used for horizontal
movement of materials. Since their introduction in 1955, they had a great impact on logistics
activities due to their dexterity, efficiency and flexibility. Generally, AGVs are part of larger
system used for the internal transportation of goods and materials among various departments
and locations within the same factory or for receiving, storage and sorting operations in shipmentareas. Thus, the main aim of an AGV-based transportation system can be summarized as:transferring/handling the right amount of the right material to the right place at the right time.
It is straightforward to understand that such aim configures a scheduling problem wheretransportation tasks have to be effectively assigned to AGVs. Literature on this topic is quite
rich, as witnessed by the survey works by Kaoud et al. (2017), Qiu et al. (2002) and Xie & Allen(2015), where several scheduling problems, differing for the considered AGV side constraints, arereviewed (Fazlollahtabar & Saidi-Mehrabad, 2015). However, as noted in De Ryck et al. (2020),
most of the contributions do not deal with battery depletion and recharge issues. To the best of
authors’ knowledge, the only work tackling the AGV scheduling problem with battery contraints(ASP-BC ) is described in Masone et al. (2021).
In a nutshell, the ASP-BC can be schematized on the basis of the following assumptions:
1) a set of AGVs must move a set of packages from a central warehouse to different workstations;2) all the AGVs are initially located at the central warehouse with fully charged batteries;3) an AGV can be loaded with a single package on each trip. Being the number of available
AGVs much lower than the number of packages, an AGV should perform more than one trip;4) the AGV battery consumption depends on the travel time and the weight carried;5) an AGV battery has to be fully recharged before it is completely depleted. The charging time
is fixed and does not depend on the residual energy;6) the ASP-BC objective is to minimize the makespan of the handling process.
For the sake of the completeness, we have to say that this problem recalls the parallel machinescheduling problem with coordinated maintenance activities, where machines cannot continuously operate longer than a pre-defined working time without performing a maintenance activity
TRISTAN XI Symposium

Original abstract submittal

M. Boccia, A. Mancuso, A. Masone and C. Sterle

2(Yoo & Lee, 2016). However, the ASP-BC has several differentiating features. From an operational point of view, we highlight that maintenance activities are scheduled considering thetime dimension (i.e. the elapsed time from the beginning of the process or the time passed fromthe last performed maintenance). Instead, in the ASP-BC, the focus is on the battery depletion
dimension, since each job consumes a specific amount of energy. From a methodological pointof view, the ASP-BC is aimed at minimizing the makespan of the handling process instead of
the sum of the job completion times. This does not allow to straightly use exact and heuristic
methods proposed for scheduling problems with maintenance activities to solve the ASP-BC,
except for a significant rethinking of the method with no effectiveness guarantee.
In this context, this work is aimed at filling this gap providing the following threefold contribution: 1) proposing an original mixed-integer linear programming (MILP) model for the
ASP-BC ; 2) developing a heuristic approach, integrated with a local search procedure, to solve
large size instances of the problem; 3) validating the proposed methods on instances built fromreal data provided by a manufacturing company.
The rest of this paper is structured as follows: the proposed MILP formulation and the heuristic
approach are sketched in 2; the computational results are reported and discussed in Section 3.

2

Problem Formulation and Heuristic Solution Method

In the following, we will refer the combination of an AGV loaded trip from warehouse to workstations and the empty trip back as a job. A job can be characterized by a duration given by
the sum of the travel time from the warehouse to the workstation and back, and the time needed
for the package load and unload operations. Moreover, each job requires a certain amount ofenergy to be performed by an AGV. Specifically, the required energy depends on the job durationand the package weight. Therefore, the number of consecutive jobs that an AGV can perform
without battery recharge is limited. On this basis, let J and K be the set of jobs and AGVs,
respectively. Moreover, we introduce a starting/ending dummy job, denoted with o/d, for each
AGV. For the sake of readability, we also define J + as J ∪ {o} and J − as J ∪ {d}. The ASP-BC
solution involves three kinds of decisions: 1) assignment of jobs to the AGVs; 2) sequencing of
the jobs on each AGV; 3) scheduling of AGV battery recharge. The objective is to minimize themakespan that is given by the maximum completion time of the last job over all the AGVs.
On this basis, we introduce the following decision variables: Cmax continuous variable equal
to the completion time of handling process; ckj continuous variables equal to the completion timeof job j on the AGV k; ekj continuous variables equal to the energy spent by the AGV k fromk binary variable equal to 1 if job j is performed
its last charge to the completion of job j; yij
immediately after job i on the k-th AGV, 0 otherwise: δjk binary variable equal to 1 if the AGV
k is recharged before performing job j, 0 otherwise.
Then, we indicate with tkj and wjk the processing time and energy required, respectively, foreach job j and for each AGV k. Finally, being r the charging time and E the battery capacity,
the ASP-BC can be formulated as follows:

min Cmax(1)

s.t.
Cmax ≥ ckj
kckj ≥ cki + tkj + rδjk − M (1 − yij)cko = 0
X X

k
yij
=1

∀j ∈ J, k ∈ K(2)∀i ∈ J + , j ∈ J, k ∈ K(3)∀k ∈ K(4)∀j ∈ J(5)i∈J + k∈K

TRISTAN XI Symposium

Original abstract submittal

M. Boccia, A. Mancuso, A. Masone and C. Sterle

X

k
yoj
=

j∈J

X
j∈J +

X

3

k
yjd
=1

∀k ∈ K(6)∀i ∈ J, K ∈ K(7)∀i, j ∈ J, k ∈ K(8)∀j ∈ J, k ∈ K(9)∀i ∈ J, j ∈ J + , k ∈ K

(10)

j∈J

X

k
yji
=

k
yij

j∈J −

ekj ≥ eki + wjk −XkM (1 − yji) − M δjkj∈J

ekj ≥ wjk − M (1 −

X

k
yij
)

i∈J +
k
ekj + wik ≤ E + M (1 − yji) + M δjk

The objective function (1) minimizes the makespan. Constraints (2) set the makespan of thehandling process greater than the completion time of any processed job. Constraints (3) ensurethat if a job j is performed on the AGV k after a job i then its completion time is greater thanthe completion time of i plus the processing time of j and the charging time (if a recharge isscheduled). Constraints (4) set to 0 the completion time of the initial dummy job. Constraints(5) guarantee that each job is performed. Constraints (6-7) ensure that each AGV can perform
one job at a time. Constraints (8, 9) set the value of the energy consumption of each AGV after
each performed job. Constraints (10) guarantee that an AGV is recharged if, performing a job,
the energy consumption would exceed its battery capacity.
The proposed formulation can be used to solve small and medium size instances of the
problem. However, for larger instances, the need of ad-hoc solution methods arises. Thus, wesolved the ASP-BC by a heuristic approach exploiting a natural decomposition of the problem
in its two assignment sub-problems: transfer jobs to charging operations; charging operations
to AGVs. These two problems are solved sequentially and can be formulated starting from the
proposed ASP-BC formulation with some specific settings. The first one is obtained solving the
ASP-BC with only one AGV. Its solution allows us to compute a lower bound for the original
ASP-BC and to determine an assignments of subset of jobs to the charging operations. The
second sub-problem fixes these assignment of jobs to the charging operations and schedules themamong the AGVs so determining an upper bound for the ASP-BC. Then, the solution is improved
through a local search procedure based on job moves that can be conceived as the well-known
add, swap, and remove operations. Thus, the heuristic configures a three-step matheuristic
approach which is able to provide both a lower and an upper bound for the ASP-BC.
For the sake of the brevity, we do not provide the details of the method. However, we pointout that the last two steps can be conceived as a single "wide" local search step which can be
performed also exploiting different metaheuristic structures (e.g., genetic algorithm or others).

3

Computational experiments and Discussion

In this section, we present the experimentation performed to evaluate and validate the proposed
three-step matheuristic approach (3S-MHA in the following). The experiments have been performed on an Intel(R) Core(TM) i7-6500U, 2.50 GHz, 8.00 GB of RAM. The 3S-MHA has beencoded in Python language. The MILP formulations are solved using Gurobi 9.1.
We considered instances with |K| equal to 2, 5, 10 and |J| equal to 50, 100 and 150. Then,we generated the job processing times, (tkj ), following a normal distribution N (µt , (µt /2)2 ), withµt ∈ {10, 20, 30}. Similarly, the job energy consumption, (wjk ), are generated following a normal distribution N (µw , (µw /2)2 ), with µw ∈ {1, 2, 4}. We point out that we considered two
independent distributions for tkj and wjk to simulate different AGV technologies, each of themcharacterized by a specific function linking carried weight, travelling time and energy consumption. The charging time r of each AGV is equal to 1 hour and the battery capacity E is equal
to 10 and it assumed to be the same for all the AGVs. Finally, for each combination of |J|, µt ,TRISTAN XI Symposium

Original abstract submittal

M. Boccia, A. Mancuso, A. Masone and C. Sterle4µw , and K we generated a set of 10 instances.
In Table 1, we report the results of the proposed approach in terms of number of optimal
solutions obtained, average and maximum percentage gap, and average time. For the sake of thebrevity, we report only the results of the best 3S-MHA implementation and setting. The results
are grouped on the basis of different parameters: number of jobs, number of AGVs, average
job duration and average energy consumption. We observe that 3S-MHA is able to determine
a great number of optimal solutions. Moreover, we point out that both the average percentage
optimality gaps and the running times are very low considering all the analyzed dimensions (jobs,
number of AGVs, average time and energy consumption). These results prove the scalability
and robustness of the proposed 3S-MHA. We also highlight that preliminary results obtained
exploiting a metaheuristic scheme in the implementation of the 3S-MHA, are further confirming
the effectiveness of the proposed approach in dealing large scale ASP-BC instances.
Table 1 – Results of the three-step matheuristic approachJ = 50J = 100
J = 150
M = 2
M = 5
M = 10Av Time = 10
Av Time = 20
Av Time = 30
Av Weight = 1
Av Weight = 2
Av Weight = 4
All# inst
270
270
270
270
270
270
270
270
270
270
270
270
810

# opt
166
201
184
237
188
125
197
181
172
210
190
150
550

Av %gap
2.76
0.56
0.29
0.1
0.41
2.55
1.04
1.2
0.822
0.56
1.71
0.8
1.02

Max %gap
40.69
16.3
2.93
1.96
14.05
40.69
20.45
40.69
28.57
16.3
40.69
13.48
40.69

Av CPU Time
17.42
67.5
220.35
92.63
104.51
108.1399.24
99107.031.29
29.8
274.18101.76

The performed experimentation derived from real data, confirm the applicability and theeffectiveness of the proposed approach. Therefore, future works will be aimed at investigating
the possibility of taking into account other operational aspects affecting the battery consumption(e.g., the AGV routing). Indeed, for the sake of completeness, we highlight that ASP-BC canbe considered as a sub-problem of the Electric Vehicle Routing Problem (EVRP ), which is a
special case of the AGV routing problems with battery constraints (Bongiovanni et al., 2019),
where scheduling decisions are integrated with routing decisions related to the movement of eachjob from a pick-up to a delivery point. Therefore, it would be interesting to extend the proposed
approach to problems involving both routing and scheduling decisions.

References
Bongiovanni, Claudia, Kaspi, Mor, & Geroliminis, Nikolas. 2019. The electric autonomous dial-a-ride
problem. Transportation Research Part B: Methodological, 122, 436–456.
De Ryck, M., Versteyhe, M., & Debrouwere, F. 2020. Automated guided vehicle systems, state-of-the-art
control algorithms and techniques. Journal of Manufacturing Systems, 54, 152–173.
Fazlollahtabar, H., & Saidi-Mehrabad, M. 2015. Methodologies to Optimize Automated Guided Vehicle
Scheduling and Routing Problems: A Review Study. J Intell Robot Syst, 77, 525–545.
Kaoud, E., El-Sharief, M. A., & El-Sebaie, M.G. 2017. Scheduling problems of automated guided vehicles
in job shop, flow shop, and container terminals. Pages 60–65 of: 2017 4th International Conferenceon Industrial Engineering and Applications (ICIEA).
Masone, A., Murino, T., Sterle, C., & Strazzullo, M. 2021. A MILP Formulation for an AutomatedGuided Vehicle Scheduling Problem with Battery Constraints. Pages 15–23 of: Dolgui, et al. (ed),APMS. Artificial Intelligence for Sustainable and Resilient Production Systems. Springer Int. Publ.
Qiu, Ling, Hsu, Wen-Jing, Huang, Shell-Ying, & Wang, Han. 2002. Scheduling and routing algorithms
for AGVs: A survey. International Journal of Production Research, 40(3), 745–760.
Xie, C., & Allen, T. T. 2015. Simulation and experimental design methods for job shop scheduling withmaterial handling: a survey. Int J Adv Manuf Technol, 80, 233–243.
Yoo, Jaewook, & Lee, Ik Sun. 2016. Parallel machine scheduling with maintenance activities. Computers& Industrial Engineering, 101, 361–371.

TRISTAN XI Symposium

Original abstract submittal