# Modelling and Optimizing an Open-Pit Truck Scheduling Problem

Authors: Yonggang Chang; Huizhi Ren; Shijie Wang
Journal: Discrete Dynamics in Nature and Society
 (2015)

---

## Abstract

This paper addresses a special truck scheduling problem in the open-pit mine with different transport revenue consideration. A mixed integer programming model is formulated to define the problem clearly and a few valid inequalities are deduced to strengthen the model. Some properties and two upper bounds of the problem are proposed. Based on these inequalities, properties, and upper bounds, a heuristic solution approach with two improvement strategies is proposed to resolve the problem and the numerical experiment demonstrates that the proposed solution approach is effective and efficient.


---

## Body

## 1. Introduction

In an open-pit mine, trucks are a kind of crucial equipment which undertakes nearly all ore and waste rock transportation [1]. Typically, the truck is loaded a full load of material (maybe ore, gangue, or other waste rocks that cover ores and thus need to be moved away) under an electric shovel, transports it to a dumping depot, dumps its loaded material, and then returns back to the shovel to carry out the next round. Figure 1 illustrates an open-pit photo and a simplified map for the road network in an open-pit mine. All of the material loading points, each of which is equipped with an electric shovel, and dumping depots are relatively constant while trucks can transport material from varied loading points and unload at different depots [2]. The efficient truck scheduling can not only reduce the truck transportation cost but also increase the shovel utilization ratio and the mine productivity [1].Figure 1
An open-pit mine and a part of its road network.
(a)
An open-pit mine
(b)
A sketch map of the open-pit road network whereL
1
,
L
3
,
…
,
L
6 represent the loading points and D
1, D
2, and D
3 represent the dumping depotsThere are plenty of researches published on the operations research in the open-pit mine, but most of them focus on the pit design and production planning [3], such as the strategic ultimate pit limit design problem [4–7] and tactical block-sequencing problem [8–11]. Among researches on the tactical and operational equipment-allocation in the open-pit mine, the stochastic feature of equipment has been emphasized. Both queuing theory and simulation were used as stochastic methodologies to model and analyse the open-pit production scheduling problem, especially in the early published literatures. For example, Manla and Ramani [12] simulated the truck haulage process which initialized the truck scheduling research. Kappas and Yegulalp [13] used the queuing theory, combined with extensions of Markovian principles, to analyze the steady-state performance of a typical truck-shovel system and estimate its operation parameters. Oraee and Asi [14] simulated the production process of trucks and shovels in Songun Copper Mine in Iran, considering fuzzy parameters on each shovel. Najor and Hagan [15] focused on stochastic behavior in the truck-shovel system and provided a model and analysis based on queuing theory. Their analysis showed that productivity can be overestimated by about 8 percent because of overlooking queuing.In some of the open-pit equipment routing and selection models, optimization methodologies, that is, integer programming and dynamic programming, were used to determine fleet size and allocation [3]. For example, White and Olson [16] applied network models, linear programming, and dynamic programming methods to the truck scheduling problem and proposed a feasible truck-dispatching system. They divided the problem into three stages. The first one was to decide the shortest paths between all locations in the mine, which is a shortest path problem actually. In the next stage, a linear program was used to determine material flows along these paths. Finally, the dynamic program assigned trucks to the optimized paths between shovels and dumps. Their truck-dispatching system not only yields significant (10–20 percent, in most cases) productivity improvements but also produced an effect on truck scheduling theory for its three-stage process [17]. And Yang et al. [18] adopted the three-stage process to resolve the truck dispatch problem.In this paper, we consider the varied transportation revenue for different material loading point and address the joint path planning and tuck dispatching problem.The outline of this paper is as follows. Section2 describes the considered open-pit truck scheduling problem with varied truck transporting revenue in detail and provides its integer programming model. In Section 3, a few valid inequalities, two properties of optimal solution, and two upper bounds for the problem are presented. In Section 4, a heuristic approach with two improvement strategies is proposed to resolve the problem. Section 5 tests the proposed upper bounds and solution approach. Section 6 concludes the paper.


## 2. Problem Description and Mathematical Model

### 2.1. Problem Description

In the open pit, there are usually several loading points and dumping depots (to be called dumps later), as shown in Figure1. At each loading point, there is always a pile of loosened ores, gangue, or waste rocks (to be referred to as material collectively), since the loading point needs a loosening blasting before the excavation operation starting. Each loading point is assumed to be equipped with one and only one electric shovel (without loss of generality, it will be viewed as two different loading points if two shovels are equipped). The electric shovel excavates and loads the loosened material onto the trucks at each loading point and the truck unloads itself with its self-discharging device at a dump. Similar to the loading point, we assume that one dump can accommodate only one truck at the same time and the unloading area of more than one truck loading positions will be viewed as several different dumps.It is worth noting that an electric shovel (or loading point) can load only one truck at the same time and a dump allows only one truck simultaneously. There is often a park for the waiting trucks near an operating electric shovel or dump. It is actually the key task to reduce the truck waiting times in the traditional truck scheduling problem.In our considered problem scenario, a truck of material from different loading point is given different transport revenue and our optimization objective will be equal to the total transport revenue completed in the scheduling horizon. The revenue per truck loading (transporting a truck of material) of different loading point is always decided by the management and the decision-making basis includes two considerations: the possible transport distance and the transport priority. The former is easy to be understood since the longer distance always causes more transport times and thus should be given more revenue. The transport priority comes from the mining sequence, which has never been modeled as a kind of constraints in the traditional research [1, 3] and/or the varied market demand. The transport revenue per truck loading can be viewed as the product of the possible transport distance and the transport priority.From the viewpoint of a scheduler who is in charge of making truck scheduling decisions in a shift (8 hours), our objective is to maximize the total transport revenues based on the given revenue value per truck loading. The decisions include the dump selection as well as the truck routing. The dump selection is virtually the same as the first-stage decisions in literature [16, 18], deciding the shortest path between all locations in the mine.The constraints to be considered include the following:(1)
loading capacity constraint: that is, each shovel (loading point) can load only one truck at the same time,
(2)
unloading capacity constraint: that is, each dump can unload only one truck at the same time,
(3)
dump selection constraint: that is, a set of candidate dumps is given for each loading point and the material from the loading point must be dumped at one of the candidate dumps.


### 2.2. The Mixed Integer Programming Model

To define and formulate the problem explicitly, the following notations need to be introduced to represent all loading points, dumps, material to be loaded in the loading points, trucks, paths parameters, and so on:S: set of available electric shovels (loading points), S
=
1,2
,
…
,
N,
S
′: S
′
=
S
∪
0, 0 denoting dummy shovels,
T: set of available trucks,
a
i: revenue per truck of material from electric shovel i, i
∈
S,
D
i: set of candidate dumps corresponding to material (waste rock or coal) loaded at electric shovel i, i
∈
S,
D
=
∪
i
∈
S
D
i: including all dumps,
H: the horizon considered in the problem,
m
i: max number of truck loadings an electric shovel i can complete at most during the horizon, i
∈
S,
K
i: K
i
=
1,2
,
…
,
m
i, set of possible trucks of rock (coal) that electric shovel i loads, i
∈
S,
k
,
i: a truck of material loaded by shovel i, i
∈
S, k
∈
K
i, hereafter referred to as truck loading k
,
i,
K
0: K
0
=
0, 0
,
0 denoting dummy truck loading,
p
i
0: loading times per truck at electric shovel i, i
∈
S,
p
j
1: unloading times per truck at depot j, j
∈
D,
P
j
i
0: times for an empty truck to move from depot j to shovel i, j
∈
D, i
∈
S,
P
i
j
1: times for a full-loaded truck to move form shovel i to depot j, j
∈
D, i
∈
S,
q
i
t: times for truck t to move from its initial position to shovel i, i
∈
S, t
∈
T,
M: very big plus number.To represent the dump selection and truck dispatch decisions, we introduce the following decision variables:(1)
x
t
k
′
i
′
k
i
=
1
,
if
truck
t
transports
k
,
i
immediatly
after
k
′
,
i
′
;
0
,
otherwise
,
for
t
∈
T
,
i
,
i
′
∈
S
′
,
k
∈
K
i
,
k
′
∈
K
i
′
;
z
k
i
=
1
,
if
truck
loading
k
,
i
is
loaded
and
transported
in
the
horizon
;
0
,
otherwise
,
for
i
∈
S
,
k
∈
K
i
;
u
j
k
′
i
′
k
i
=
1
,
if
material
k
,
i
is
dumped
immediatly
after
k
′
,
i
′
at
despot
j
;
0
,
otherwise
,
for
∈
D
i
∩
D
i
′
i
,
i
′
∈
S
,
k
∈
K
i
,
k
′
∈
K
i
′
;
y
k
i
j
=
1
,
if
material
k
,
i
is
dumped
at
despot
j
;
0
,
otherwise
,
for
j
∈
D
i
i
∈
S
,
k
∈
K
i
;
c
k
i
0 is complete time of loading material k
,
i, for i
∈
S, k
∈
K
i
′;
c
k
i
1 is complete time of unloading material k
,
i, for i
∈
S, k
∈
K
i
′.Based on the above notations, the problem can be formulated as the following integer programming model (similar to model in Tang et al. [19] which involved a truck scheduling problem in container terminals):(2)
Max
⁡
∑
i
∈
S
∑
k
∈
K
i
a
i
z
k
i
(3)
s
.
t
.
c
k
+
1
,
i
0
-
c
k
i
0
≥
p
i
0
,
i
∈
S
,
k
∈
K
i
(4)
c
k
i
1
-
c
k
′
i
′
1
≥
p
j
1
-
M
1
-
u
j
k
′
i
′
k
i
,
i
,
i
′
∈
S
,
k
∈
K
i
,
k
′
∈
K
i
′
,
j
∈
D
i
∩
D
i
′
(5)
c
k
i
1
-
c
k
i
0
≥
∑
j
∈
D
y
k
i
j
P
i
j
+
p
j
1
,
i
∈
S
,
k
∈
K
i
(6)
c
k
i
0
-
c
k
′
i
′
1
≥
∑
j
∈
D
y
k
′
i
′
j
P
j
i
+
p
i
0
-
M
1
-
∑
t
∈
T
x
t
k
′
i
′
k
i
,
i
,
i
′
∈
S
,
k
∈
K
i
,
k
′
∈
K
i
′
(7)
c
k
i
0
≥
∑
t
∈
T
x
t
,
0,0
,
k
,
i
q
i
t
+
p
i
0
-
M
1
-
∑
t
∈
T
x
t
,
0,0
,
k
,
i
,
i
∈
S
,
k
∈
K
i
(8)
c
k
i
1
≤
H
+
M
1
-
z
k
i
,
i
∈
S
,
k
∈
K
i
′
(9)
∑
i
∈
S
′
∑
k
∈
K
i
x
t
k
′
i
′
k
i
=
z
k
′
i
′
,
t
∈
T
,
i
′
∈
S
,
k
′
∈
K
i
′
(10)
∑
i
′
∈
S
′
∑
k
′
∈
K
i
′
x
t
k
′
i
′
k
i
=
z
k
i
,
t
∈
T
,
i
∈
S
,
k
∈
K
i
(11)
x
t
k
i
k
i
=
0
,
t
∈
T
,
i
∈
S
,
k
∈
K
i
(12)
∑
i
∈
S
′
∑
k
∈
K
i
x
t
,
k
,
i
,
0,0
=
∑
i
∈
S
′
∑
k
∈
K
i
x
t
,
0,0
,
k
,
i
=
1
,
t
∈
T
(13)
∑
i
′
∈
S
′
∑
k
′
∈
K
i
′
u
j
k
′
i
′
k
i
=
∑
i
′
∈
S
′
∑
k
∖
∈
K
i
′
u
j
k
i
k
′
i
′
=
z
k
i
,
t
∈
T
,
i
∈
S
,
k
∈
K
i
′
(14)
u
j
k
i
k
i
=
0
,
j
∈
D
i
,
i
∈
S
,
k
∈
K
i
′
(15)
∑
i
∈
S
∑
k
∈
K
i
u
j
,
k
,
i
,
0,0
=
∑
i
∈
S
∑
k
∈
K
i
u
j
,
0,0
,
k
,
i
=
1
,
j
∈
D
(16)
∑
j
∈
D
i
y
k
i
j
=
z
k
i
,
i
∈
S
,
k
∈
K
i
.The objective function (2) of the model maximizes the total transport value, that is, sum of transport revenue of all truck loadings unloaded in horizon H. Constraints (3) can provide each truck with enough loading times between it and its adjacent trucks under the same shovel. Similarly, constraints (4) ensure enough time to unload material between two adjacent trucks that continuously dump at the same depot. Constraints (5) guarantee that each truck has enough traveling time to transport material from the involved shovel to depot while constraints (6) provide a truck with enough empty traveling time to return its next loading shovel. Constraints (7) guarantee that each truck starts from its initial position and reserves enough empty traveling time to reach its first loading spot before the involved shovel starts the truck loading operation. Constraints (8) define the variable z
k
i; that is, set z
k
i
=
1 if truck loading k
,
i can be finished in horizon H. Constraints (9) and (10) guarantee that each valid truck loading (z
k
i
=
1) is assigned to one and only one truck and each truck can operate continuously. Constraints (11) prevent truck loading self-loop. Constraints (12) state that one and only one truck loading serves as the head (last) truck loading for each available truck. Similar to constraints (9) and (10), constraints (13) state that each valid truck loading is assigned to one and only one dumping depot and each dumping depot operates continuously. Constraints (14) perform same as constraints (11), prohibiting the self-loop in unloading sequence. Similar to constraints (12), constraints (15) state that one and only one truck loading serves as the head (last) truck for each dumping depot. Constraints (16) define the relationship between variables y
k
i
j and z
k
i; that is, each valid truck loading has one and only one dumping depot.


## 2.1. Problem Description

In the open pit, there are usually several loading points and dumping depots (to be called dumps later), as shown in Figure1. At each loading point, there is always a pile of loosened ores, gangue, or waste rocks (to be referred to as material collectively), since the loading point needs a loosening blasting before the excavation operation starting. Each loading point is assumed to be equipped with one and only one electric shovel (without loss of generality, it will be viewed as two different loading points if two shovels are equipped). The electric shovel excavates and loads the loosened material onto the trucks at each loading point and the truck unloads itself with its self-discharging device at a dump. Similar to the loading point, we assume that one dump can accommodate only one truck at the same time and the unloading area of more than one truck loading positions will be viewed as several different dumps.It is worth noting that an electric shovel (or loading point) can load only one truck at the same time and a dump allows only one truck simultaneously. There is often a park for the waiting trucks near an operating electric shovel or dump. It is actually the key task to reduce the truck waiting times in the traditional truck scheduling problem.In our considered problem scenario, a truck of material from different loading point is given different transport revenue and our optimization objective will be equal to the total transport revenue completed in the scheduling horizon. The revenue per truck loading (transporting a truck of material) of different loading point is always decided by the management and the decision-making basis includes two considerations: the possible transport distance and the transport priority. The former is easy to be understood since the longer distance always causes more transport times and thus should be given more revenue. The transport priority comes from the mining sequence, which has never been modeled as a kind of constraints in the traditional research [1, 3] and/or the varied market demand. The transport revenue per truck loading can be viewed as the product of the possible transport distance and the transport priority.From the viewpoint of a scheduler who is in charge of making truck scheduling decisions in a shift (8 hours), our objective is to maximize the total transport revenues based on the given revenue value per truck loading. The decisions include the dump selection as well as the truck routing. The dump selection is virtually the same as the first-stage decisions in literature [16, 18], deciding the shortest path between all locations in the mine.The constraints to be considered include the following:(1)
loading capacity constraint: that is, each shovel (loading point) can load only one truck at the same time,
(2)
unloading capacity constraint: that is, each dump can unload only one truck at the same time,
(3)
dump selection constraint: that is, a set of candidate dumps is given for each loading point and the material from the loading point must be dumped at one of the candidate dumps.


## 2.2. The Mixed Integer Programming Model

To define and formulate the problem explicitly, the following notations need to be introduced to represent all loading points, dumps, material to be loaded in the loading points, trucks, paths parameters, and so on:S: set of available electric shovels (loading points), S
=
1,2
,
…
,
N,
S
′: S
′
=
S
∪
0, 0 denoting dummy shovels,
T: set of available trucks,
a
i: revenue per truck of material from electric shovel i, i
∈
S,
D
i: set of candidate dumps corresponding to material (waste rock or coal) loaded at electric shovel i, i
∈
S,
D
=
∪
i
∈
S
D
i: including all dumps,
H: the horizon considered in the problem,
m
i: max number of truck loadings an electric shovel i can complete at most during the horizon, i
∈
S,
K
i: K
i
=
1,2
,
…
,
m
i, set of possible trucks of rock (coal) that electric shovel i loads, i
∈
S,
k
,
i: a truck of material loaded by shovel i, i
∈
S, k
∈
K
i, hereafter referred to as truck loading k
,
i,
K
0: K
0
=
0, 0
,
0 denoting dummy truck loading,
p
i
0: loading times per truck at electric shovel i, i
∈
S,
p
j
1: unloading times per truck at depot j, j
∈
D,
P
j
i
0: times for an empty truck to move from depot j to shovel i, j
∈
D, i
∈
S,
P
i
j
1: times for a full-loaded truck to move form shovel i to depot j, j
∈
D, i
∈
S,
q
i
t: times for truck t to move from its initial position to shovel i, i
∈
S, t
∈
T,
M: very big plus number.To represent the dump selection and truck dispatch decisions, we introduce the following decision variables:(1)
x
t
k
′
i
′
k
i
=
1
,
if
truck
t
transports
k
,
i
immediatly
after
k
′
,
i
′
;
0
,
otherwise
,
for
t
∈
T
,
i
,
i
′
∈
S
′
,
k
∈
K
i
,
k
′
∈
K
i
′
;
z
k
i
=
1
,
if
truck
loading
k
,
i
is
loaded
and
transported
in
the
horizon
;
0
,
otherwise
,
for
i
∈
S
,
k
∈
K
i
;
u
j
k
′
i
′
k
i
=
1
,
if
material
k
,
i
is
dumped
immediatly
after
k
′
,
i
′
at
despot
j
;
0
,
otherwise
,
for
∈
D
i
∩
D
i
′
i
,
i
′
∈
S
,
k
∈
K
i
,
k
′
∈
K
i
′
;
y
k
i
j
=
1
,
if
material
k
,
i
is
dumped
at
despot
j
;
0
,
otherwise
,
for
j
∈
D
i
i
∈
S
,
k
∈
K
i
;
c
k
i
0 is complete time of loading material k
,
i, for i
∈
S, k
∈
K
i
′;
c
k
i
1 is complete time of unloading material k
,
i, for i
∈
S, k
∈
K
i
′.Based on the above notations, the problem can be formulated as the following integer programming model (similar to model in Tang et al. [19] which involved a truck scheduling problem in container terminals):(2)
Max
⁡
∑
i
∈
S
∑
k
∈
K
i
a
i
z
k
i
(3)
s
.
t
.
c
k
+
1
,
i
0
-
c
k
i
0
≥
p
i
0
,
i
∈
S
,
k
∈
K
i
(4)
c
k
i
1
-
c
k
′
i
′
1
≥
p
j
1
-
M
1
-
u
j
k
′
i
′
k
i
,
i
,
i
′
∈
S
,
k
∈
K
i
,
k
′
∈
K
i
′
,
j
∈
D
i
∩
D
i
′
(5)
c
k
i
1
-
c
k
i
0
≥
∑
j
∈
D
y
k
i
j
P
i
j
+
p
j
1
,
i
∈
S
,
k
∈
K
i
(6)
c
k
i
0
-
c
k
′
i
′
1
≥
∑
j
∈
D
y
k
′
i
′
j
P
j
i
+
p
i
0
-
M
1
-
∑
t
∈
T
x
t
k
′
i
′
k
i
,
i
,
i
′
∈
S
,
k
∈
K
i
,
k
′
∈
K
i
′
(7)
c
k
i
0
≥
∑
t
∈
T
x
t
,
0,0
,
k
,
i
q
i
t
+
p
i
0
-
M
1
-
∑
t
∈
T
x
t
,
0,0
,
k
,
i
,
i
∈
S
,
k
∈
K
i
(8)
c
k
i
1
≤
H
+
M
1
-
z
k
i
,
i
∈
S
,
k
∈
K
i
′
(9)
∑
i
∈
S
′
∑
k
∈
K
i
x
t
k
′
i
′
k
i
=
z
k
′
i
′
,
t
∈
T
,
i
′
∈
S
,
k
′
∈
K
i
′
(10)
∑
i
′
∈
S
′
∑
k
′
∈
K
i
′
x
t
k
′
i
′
k
i
=
z
k
i
,
t
∈
T
,
i
∈
S
,
k
∈
K
i
(11)
x
t
k
i
k
i
=
0
,
t
∈
T
,
i
∈
S
,
k
∈
K
i
(12)
∑
i
∈
S
′
∑
k
∈
K
i
x
t
,
k
,
i
,
0,0
=
∑
i
∈
S
′
∑
k
∈
K
i
x
t
,
0,0
,
k
,
i
=
1
,
t
∈
T
(13)
∑
i
′
∈
S
′
∑
k
′
∈
K
i
′
u
j
k
′
i
′
k
i
=
∑
i
′
∈
S
′
∑
k
∖
∈
K
i
′
u
j
k
i
k
′
i
′
=
z
k
i
,
t
∈
T
,
i
∈
S
,
k
∈
K
i
′
(14)
u
j
k
i
k
i
=
0
,
j
∈
D
i
,
i
∈
S
,
k
∈
K
i
′
(15)
∑
i
∈
S
∑
k
∈
K
i
u
j
,
k
,
i
,
0,0
=
∑
i
∈
S
∑
k
∈
K
i
u
j
,
0,0
,
k
,
i
=
1
,
j
∈
D
(16)
∑
j
∈
D
i
y
k
i
j
=
z
k
i
,
i
∈
S
,
k
∈
K
i
.The objective function (2) of the model maximizes the total transport value, that is, sum of transport revenue of all truck loadings unloaded in horizon H. Constraints (3) can provide each truck with enough loading times between it and its adjacent trucks under the same shovel. Similarly, constraints (4) ensure enough time to unload material between two adjacent trucks that continuously dump at the same depot. Constraints (5) guarantee that each truck has enough traveling time to transport material from the involved shovel to depot while constraints (6) provide a truck with enough empty traveling time to return its next loading shovel. Constraints (7) guarantee that each truck starts from its initial position and reserves enough empty traveling time to reach its first loading spot before the involved shovel starts the truck loading operation. Constraints (8) define the variable z
k
i; that is, set z
k
i
=
1 if truck loading k
,
i can be finished in horizon H. Constraints (9) and (10) guarantee that each valid truck loading (z
k
i
=
1) is assigned to one and only one truck and each truck can operate continuously. Constraints (11) prevent truck loading self-loop. Constraints (12) state that one and only one truck loading serves as the head (last) truck loading for each available truck. Similar to constraints (9) and (10), constraints (13) state that each valid truck loading is assigned to one and only one dumping depot and each dumping depot operates continuously. Constraints (14) perform same as constraints (11), prohibiting the self-loop in unloading sequence. Similar to constraints (12), constraints (15) state that one and only one truck loading serves as the head (last) truck for each dumping depot. Constraints (16) define the relationship between variables y
k
i
j and z
k
i; that is, each valid truck loading has one and only one dumping depot.


## 3. Valid Inequalities, Property, and Upper Bounds for the Problem

### 3.1. Valid Inequalities

In this section, a few valid inequalities are introduced. To the problem definition, the model in Section2.2 is already adequate and all the valid inequalities are redundant, but they can reduce the computing time if we attempt to directly solve the model through commercial optimization software, such as CPLEX. In addition, the valid inequalities are also helpful for constructing the heuristic approach.


#### 3.1.1. Electric Shovel Capacity Inequality

Consider(17)
∑
k
∈
K
i
z
k
i
p
i
0
≤
H
-
min
⁡
t
∈
T
⁡
q
i
t
-
min
⁡
j
∈
D
i
⁡
p
i
j
1
+
p
j
1
,
i
∈
S
.Inequality (17) gives the maximum possible number of trucks each electric shovel can finish in the horizon. In the inequality, H
-
min
⁡
t
∈
T
⁡
q
i
t
-
min
⁡
j
∈
D
i
⁡
p
i
j
1 is the practical time limit for shovel i, where min
⁡
t
∈
T
⁡
q
i
t is the time for the nearest empty truck to move from its initial position to shovel i, that is, the least possible times before shovel i starting the first truck-loading, and min
⁡
j
∈
D
i
⁡
{
p
i
j
1
+
p
j
1
} is the permitted least retained time to transport and unload the last truck loaded by shovel i.


#### 3.1.2. Unloading Capacity Inequality

Consider(18)
∑
i
∈
S
∑
k
∈
K
i
y
k
i
j
p
j
1
≤
H
-
min
⁡
i
∈
{
i
′
∣
j
∈
D
i
′
}
⁡
min
⁡
t
∈
T
⁡
q
i
t
+
p
i
0
+
p
i
j
1
,
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
i
j
∈
D
.Inequality (18) gives the maximum possible number of trucks each unloading depot can unload in the horizon. In the inequality, H
-
min
⁡
i
∈
i
′
∣
j
∈
D
i
′
⁡
{
min
⁡
t
∈
T
⁡
q
i
t
+
p
i
0
+
p
i
j
1
} is the practical time limit for depot j, where min
⁡
i
∈
i
′
∣
j
∈
D
i
′
⁡
{
min
⁡
t
∈
T
⁡
q
i
t
+
p
i
0
+
p
i
j
1
} is the earliest possible starting time of unloading the first truck in depot j.


#### 3.1.3. Variables Relationship Inequality

Consider(19)
z
k
i
≤
z
k
′
i
,
k
≤
k
′
,
i
∈
S
.Inequality (19) comes from the material transportation sequence as ensured by formula (3), where truck loading k
,
i is doomed to be transported before k
′
,
i when k
≤
k
′ stands.


### 3.2. Property of the Optimal Solution

For the above, define open-pit truck scheduling problem; we observe two properties for the optimal solutions. Some new concepts need to be introduced to describe the properties.Definition 1.
An empty truck, starting from a depotj, j
∈
D
i, moves to a shovel i, i
∈
S, loads material (with shovel i), transports it to a depot j
′
,
j
∈
D
i, and unloads the material (e.g., travelling from dump D
1 to loading point L
1 and to D
3 in Figure 2). The whole movement process is called atruck round trip, denoted by trip j
,
i
,
j
′.Figure 2
Illustration of the truck round trip.It is noteworthy that the end depot involved in a truck round trip can be the same as the starting depot.Definition 2.
For any a truck round tripj
,
i
,
j
′, j
∈
D, j
′
∈
D
i, i
∈
S, e
j
i
j
′
=
a
i
/
(
P
j
i
0
+
P
i
j
′
1
+
p
i
0
+
p
j
1
) is called trip transport value.Roughly speaking, the trip transport value can be viewed as the truck transport revenue per unit time for some truck round trip. There is an intuitionistic suggestion from the definition that trucks should be dispatched to the trip with higher trip transportation value.Definition 3.
The truck operation times, excluding the below three classes of invaluable time, are calledvaluable times: (1)
times when truck waiting at an electronic shovel for loading due to another truck occupies the same shovel,
(2)
times when truck waiting at a depot for unloading due to another truck occupies the depot,
(3)
times for the unfinished round trip if a truck cannot unload its last truck loading in the horizon.It is noteworthy that the trucks are assumed not to travel more time than the given travelling time (p
i
j
1 and p
j
i
0) through the path.Property 1.
If the initial position of each truck is one of the depots, the objective value of a feasible solution to the joint problem is equal to(20)
∑
t
∈
T
∑
(
j
,
i
,
j
′
)
∈
Ψ
l
t
,
j
,
i
,
j
′
e
j
,
i
,
j
′
,where l
t
,
j
,
i
,
j
′ denotes the total valuable times that truck t has spent on trip j
,
i
,
j
′ in the solution and Ψ denotes the set of all truck round trips.The property provides another formulation for the problem objective function and will play an important role in constructing the upper bound.Property 2.
In a feasible solution for the joint problem, the total valuable time spent on truck round tripj
,
i
,
j
′, j
∈
D, j
′
∈
D
i, i
∈
S, is not larger than P
j
i
0
+
P
i
j
′
1
+
p
i
0
+
p
j
1
·
min
⁡
Z
i
0
,
Z
j
′
1, where Z
i
0 and Z
j
′
1 denote the maximum loading capacity of electronic shovel i and maximum unloading capacity of dump j
′, respectively.In Property2, Z
i
0 and Z
j
′
1 can be obtained through formulae (17) and (18), respectively.


### 3.3. Upper Bounds

Since the number of trucks loadings each electronic shovel can finish is limited in the horizon, there is obviously the below upper bound for the problem.


#### 3.3.1. Upper Bound 1

The objective value of the optimal solution cannot be larger than∑
i
∈
S
a
i
Z
i
0.In view of both the truck transport capacity and shovel loading capacity, another more tightened upper bound can be obtained. LetN
T denote the number of available trucks; then C
T
=
H
·
N
T denotes the total available truck times involved in the problem. Let r
i denote the optimal truck round trip involving shovel i, i
∈
S; that is to say, trip r
i requires the shortest valuable truck times in the trips that transport materials from shovel i to one of the available dumps, and P
i
* and E
i
* denote the required valuable truck times and trip transport value corresponding to trip r
i, respectively.It is assumed thati
1
,
i
2
,
…
,
i
N is the shovel sequence in the descending order of E
i
*; that is, E
i
1
*
≥
E
i
2
*
≥
⋯
≥
E
i
N
* and i
1
,
i
2
,
…
,
i
N
=
S.Upper bound 2 can be described and formulated clearly, based on the above notations and assumption.


#### 3.3.2. Upper Bound 2

The objective value of the optimal solution must not be larger than the following piecewise function value:(21)
f
C
T
=
E
i
1
*
C
T
,
C
T
≤
Z
i
1
0
P
i
1
*
a
i
1
Z
i
1
0
+
E
i
2
*
C
T
-
Z
i
1
0
P
i
1
*
,
Z
i
1
0
P
i
1
*
≤
C
T
≤
Z
i
1
0
P
i
1
*
+
Z
i
2
0
P
i
2
*
⋮
∑
n
=
1
N
-
2
a
i
n
Z
i
n
0
+
E
i
N
-
1
*
C
T
-
∑
n
=
1
N
-
2
Z
i
n
0
P
i
n
*
,
∑
n
=
1
N
-
2
Z
i
n
0
P
i
n
*
≤
C
T
≤
∑
n
=
1
N
-
2
Z
i
n
0
P
i
n
*
+
Z
i
N
-
1
0
P
i
N
-
1
*
∑
n
=
1
N
-
1
a
i
n
Z
i
n
0
+
E
i
N
*
C
T
-
∑
n
=
1
N
-
1
Z
i
n
0
P
i
n
*
,
∑
n
=
1
N
-
1
Z
i
n
0
P
i
n
*
≤
C
T
≤
∑
n
=
1
N
-
1
Z
i
n
0
P
i
n
*
+
Z
i
N
0
P
i
N
*
.The underlying idea of upper bound is that the truck should be dispatched to the electronic shovel and round trip with transport value as high as possible to maximize the total revenues.


## 3.1. Valid Inequalities

In this section, a few valid inequalities are introduced. To the problem definition, the model in Section2.2 is already adequate and all the valid inequalities are redundant, but they can reduce the computing time if we attempt to directly solve the model through commercial optimization software, such as CPLEX. In addition, the valid inequalities are also helpful for constructing the heuristic approach.


### 3.1.1. Electric Shovel Capacity Inequality

Consider(17)
∑
k
∈
K
i
z
k
i
p
i
0
≤
H
-
min
⁡
t
∈
T
⁡
q
i
t
-
min
⁡
j
∈
D
i
⁡
p
i
j
1
+
p
j
1
,
i
∈
S
.Inequality (17) gives the maximum possible number of trucks each electric shovel can finish in the horizon. In the inequality, H
-
min
⁡
t
∈
T
⁡
q
i
t
-
min
⁡
j
∈
D
i
⁡
p
i
j
1 is the practical time limit for shovel i, where min
⁡
t
∈
T
⁡
q
i
t is the time for the nearest empty truck to move from its initial position to shovel i, that is, the least possible times before shovel i starting the first truck-loading, and min
⁡
j
∈
D
i
⁡
{
p
i
j
1
+
p
j
1
} is the permitted least retained time to transport and unload the last truck loaded by shovel i.


### 3.1.2. Unloading Capacity Inequality

Consider(18)
∑
i
∈
S
∑
k
∈
K
i
y
k
i
j
p
j
1
≤
H
-
min
⁡
i
∈
{
i
′
∣
j
∈
D
i
′
}
⁡
min
⁡
t
∈
T
⁡
q
i
t
+
p
i
0
+
p
i
j
1
,
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
i
j
∈
D
.Inequality (18) gives the maximum possible number of trucks each unloading depot can unload in the horizon. In the inequality, H
-
min
⁡
i
∈
i
′
∣
j
∈
D
i
′
⁡
{
min
⁡
t
∈
T
⁡
q
i
t
+
p
i
0
+
p
i
j
1
} is the practical time limit for depot j, where min
⁡
i
∈
i
′
∣
j
∈
D
i
′
⁡
{
min
⁡
t
∈
T
⁡
q
i
t
+
p
i
0
+
p
i
j
1
} is the earliest possible starting time of unloading the first truck in depot j.


### 3.1.3. Variables Relationship Inequality

Consider(19)
z
k
i
≤
z
k
′
i
,
k
≤
k
′
,
i
∈
S
.Inequality (19) comes from the material transportation sequence as ensured by formula (3), where truck loading k
,
i is doomed to be transported before k
′
,
i when k
≤
k
′ stands.


## 3.1.1. Electric Shovel Capacity Inequality

Consider(17)
∑
k
∈
K
i
z
k
i
p
i
0
≤
H
-
min
⁡
t
∈
T
⁡
q
i
t
-
min
⁡
j
∈
D
i
⁡
p
i
j
1
+
p
j
1
,
i
∈
S
.Inequality (17) gives the maximum possible number of trucks each electric shovel can finish in the horizon. In the inequality, H
-
min
⁡
t
∈
T
⁡
q
i
t
-
min
⁡
j
∈
D
i
⁡
p
i
j
1 is the practical time limit for shovel i, where min
⁡
t
∈
T
⁡
q
i
t is the time for the nearest empty truck to move from its initial position to shovel i, that is, the least possible times before shovel i starting the first truck-loading, and min
⁡
j
∈
D
i
⁡
{
p
i
j
1
+
p
j
1
} is the permitted least retained time to transport and unload the last truck loaded by shovel i.


## 3.1.2. Unloading Capacity Inequality

Consider(18)
∑
i
∈
S
∑
k
∈
K
i
y
k
i
j
p
j
1
≤
H
-
min
⁡
i
∈
{
i
′
∣
j
∈
D
i
′
}
⁡
min
⁡
t
∈
T
⁡
q
i
t
+
p
i
0
+
p
i
j
1
,
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
h
i
j
∈
D
.Inequality (18) gives the maximum possible number of trucks each unloading depot can unload in the horizon. In the inequality, H
-
min
⁡
i
∈
i
′
∣
j
∈
D
i
′
⁡
{
min
⁡
t
∈
T
⁡
q
i
t
+
p
i
0
+
p
i
j
1
} is the practical time limit for depot j, where min
⁡
i
∈
i
′
∣
j
∈
D
i
′
⁡
{
min
⁡
t
∈
T
⁡
q
i
t
+
p
i
0
+
p
i
j
1
} is the earliest possible starting time of unloading the first truck in depot j.


## 3.1.3. Variables Relationship Inequality

Consider(19)
z
k
i
≤
z
k
′
i
,
k
≤
k
′
,
i
∈
S
.Inequality (19) comes from the material transportation sequence as ensured by formula (3), where truck loading k
,
i is doomed to be transported before k
′
,
i when k
≤
k
′ stands.


## 3.2. Property of the Optimal Solution

For the above, define open-pit truck scheduling problem; we observe two properties for the optimal solutions. Some new concepts need to be introduced to describe the properties.Definition 1.
An empty truck, starting from a depotj, j
∈
D
i, moves to a shovel i, i
∈
S, loads material (with shovel i), transports it to a depot j
′
,
j
∈
D
i, and unloads the material (e.g., travelling from dump D
1 to loading point L
1 and to D
3 in Figure 2). The whole movement process is called atruck round trip, denoted by trip j
,
i
,
j
′.Figure 2
Illustration of the truck round trip.It is noteworthy that the end depot involved in a truck round trip can be the same as the starting depot.Definition 2.
For any a truck round tripj
,
i
,
j
′, j
∈
D, j
′
∈
D
i, i
∈
S, e
j
i
j
′
=
a
i
/
(
P
j
i
0
+
P
i
j
′
1
+
p
i
0
+
p
j
1
) is called trip transport value.Roughly speaking, the trip transport value can be viewed as the truck transport revenue per unit time for some truck round trip. There is an intuitionistic suggestion from the definition that trucks should be dispatched to the trip with higher trip transportation value.Definition 3.
The truck operation times, excluding the below three classes of invaluable time, are calledvaluable times: (1)
times when truck waiting at an electronic shovel for loading due to another truck occupies the same shovel,
(2)
times when truck waiting at a depot for unloading due to another truck occupies the depot,
(3)
times for the unfinished round trip if a truck cannot unload its last truck loading in the horizon.It is noteworthy that the trucks are assumed not to travel more time than the given travelling time (p
i
j
1 and p
j
i
0) through the path.Property 1.
If the initial position of each truck is one of the depots, the objective value of a feasible solution to the joint problem is equal to(20)
∑
t
∈
T
∑
(
j
,
i
,
j
′
)
∈
Ψ
l
t
,
j
,
i
,
j
′
e
j
,
i
,
j
′
,where l
t
,
j
,
i
,
j
′ denotes the total valuable times that truck t has spent on trip j
,
i
,
j
′ in the solution and Ψ denotes the set of all truck round trips.The property provides another formulation for the problem objective function and will play an important role in constructing the upper bound.Property 2.
In a feasible solution for the joint problem, the total valuable time spent on truck round tripj
,
i
,
j
′, j
∈
D, j
′
∈
D
i, i
∈
S, is not larger than P
j
i
0
+
P
i
j
′
1
+
p
i
0
+
p
j
1
·
min
⁡
Z
i
0
,
Z
j
′
1, where Z
i
0 and Z
j
′
1 denote the maximum loading capacity of electronic shovel i and maximum unloading capacity of dump j
′, respectively.In Property2, Z
i
0 and Z
j
′
1 can be obtained through formulae (17) and (18), respectively.


## 3.3. Upper Bounds

Since the number of trucks loadings each electronic shovel can finish is limited in the horizon, there is obviously the below upper bound for the problem.


### 3.3.1. Upper Bound 1

The objective value of the optimal solution cannot be larger than∑
i
∈
S
a
i
Z
i
0.In view of both the truck transport capacity and shovel loading capacity, another more tightened upper bound can be obtained. LetN
T denote the number of available trucks; then C
T
=
H
·
N
T denotes the total available truck times involved in the problem. Let r
i denote the optimal truck round trip involving shovel i, i
∈
S; that is to say, trip r
i requires the shortest valuable truck times in the trips that transport materials from shovel i to one of the available dumps, and P
i
* and E
i
* denote the required valuable truck times and trip transport value corresponding to trip r
i, respectively.It is assumed thati
1
,
i
2
,
…
,
i
N is the shovel sequence in the descending order of E
i
*; that is, E
i
1
*
≥
E
i
2
*
≥
⋯
≥
E
i
N
* and i
1
,
i
2
,
…
,
i
N
=
S.Upper bound 2 can be described and formulated clearly, based on the above notations and assumption.


### 3.3.2. Upper Bound 2

The objective value of the optimal solution must not be larger than the following piecewise function value:(21)
f
C
T
=
E
i
1
*
C
T
,
C
T
≤
Z
i
1
0
P
i
1
*
a
i
1
Z
i
1
0
+
E
i
2
*
C
T
-
Z
i
1
0
P
i
1
*
,
Z
i
1
0
P
i
1
*
≤
C
T
≤
Z
i
1
0
P
i
1
*
+
Z
i
2
0
P
i
2
*
⋮
∑
n
=
1
N
-
2
a
i
n
Z
i
n
0
+
E
i
N
-
1
*
C
T
-
∑
n
=
1
N
-
2
Z
i
n
0
P
i
n
*
,
∑
n
=
1
N
-
2
Z
i
n
0
P
i
n
*
≤
C
T
≤
∑
n
=
1
N
-
2
Z
i
n
0
P
i
n
*
+
Z
i
N
-
1
0
P
i
N
-
1
*
∑
n
=
1
N
-
1
a
i
n
Z
i
n
0
+
E
i
N
*
C
T
-
∑
n
=
1
N
-
1
Z
i
n
0
P
i
n
*
,
∑
n
=
1
N
-
1
Z
i
n
0
P
i
n
*
≤
C
T
≤
∑
n
=
1
N
-
1
Z
i
n
0
P
i
n
*
+
Z
i
N
0
P
i
N
*
.The underlying idea of upper bound is that the truck should be dispatched to the electronic shovel and round trip with transport value as high as possible to maximize the total revenues.


## 3.3.1. Upper Bound 1

The objective value of the optimal solution cannot be larger than∑
i
∈
S
a
i
Z
i
0.In view of both the truck transport capacity and shovel loading capacity, another more tightened upper bound can be obtained. LetN
T denote the number of available trucks; then C
T
=
H
·
N
T denotes the total available truck times involved in the problem. Let r
i denote the optimal truck round trip involving shovel i, i
∈
S; that is to say, trip r
i requires the shortest valuable truck times in the trips that transport materials from shovel i to one of the available dumps, and P
i
* and E
i
* denote the required valuable truck times and trip transport value corresponding to trip r
i, respectively.It is assumed thati
1
,
i
2
,
…
,
i
N is the shovel sequence in the descending order of E
i
*; that is, E
i
1
*
≥
E
i
2
*
≥
⋯
≥
E
i
N
* and i
1
,
i
2
,
…
,
i
N
=
S.Upper bound 2 can be described and formulated clearly, based on the above notations and assumption.


## 3.3.2. Upper Bound 2

The objective value of the optimal solution must not be larger than the following piecewise function value:(21)
f
C
T
=
E
i
1
*
C
T
,
C
T
≤
Z
i
1
0
P
i
1
*
a
i
1
Z
i
1
0
+
E
i
2
*
C
T
-
Z
i
1
0
P
i
1
*
,
Z
i
1
0
P
i
1
*
≤
C
T
≤
Z
i
1
0
P
i
1
*
+
Z
i
2
0
P
i
2
*
⋮
∑
n
=
1
N
-
2
a
i
n
Z
i
n
0
+
E
i
N
-
1
*
C
T
-
∑
n
=
1
N
-
2
Z
i
n
0
P
i
n
*
,
∑
n
=
1
N
-
2
Z
i
n
0
P
i
n
*
≤
C
T
≤
∑
n
=
1
N
-
2
Z
i
n
0
P
i
n
*
+
Z
i
N
-
1
0
P
i
N
-
1
*
∑
n
=
1
N
-
1
a
i
n
Z
i
n
0
+
E
i
N
*
C
T
-
∑
n
=
1
N
-
1
Z
i
n
0
P
i
n
*
,
∑
n
=
1
N
-
1
Z
i
n
0
P
i
n
*
≤
C
T
≤
∑
n
=
1
N
-
1
Z
i
n
0
P
i
n
*
+
Z
i
N
0
P
i
N
*
.The underlying idea of upper bound is that the truck should be dispatched to the electronic shovel and round trip with transport value as high as possible to maximize the total revenues.


## 4. Heuristic Solution Method to the Problem

### 4.1. A Constructive Heuristic Method to Generate Initial Solution

In the practical scheduling process, truck waiting times are often inevitable and thus the conception of expected real-time transport value is introduced here.Definition 4.
In the practical truck scheduling,e
j
i
j
′
*
=
a
i
/
(
P
j
i
0
+
P
i
j
′
1
+
p
i
0
+
p
j
1
+
δ
), j
,
i
,
j
′, j
∈
D, j
′
∈
D
i, i
∈
S,  is called expected real-time transport value (ERTV) for a possible truck round trip selection, where δ is the expected truck waiting time (invaluable truck times) during the whole trip.Based on the above definition, a constructive heuristic method can be introduced to generate the initial solution. It includes the following steps.Step A1. Build a truck set S
idle, including all trucks that are not assigned to a round trip or just finished a round trip in the scheduling, and set S
idle to include all trucks in the initial state.Build a truck setS
running and let S
running
=
∅ in the initial state.Build a truck scheduling information tableT
truck, a shovel dispatch information table T
shovel, and a dump scheduling information table T
dump. Initialize the three information tables with T
truck
=
∅, T
shovel
=
∅, and T
dump
=
∅.Step A2. If S
idle
≠
∅, for each truck in S
idle, construct the corresponding round trips, compute their expected real-time transport values in the current state (referring to T
truck, T
shovel, and T
dump), and record the trip with the highest ERTV and its ERTV; otherwise, go to Step A
4.Step A3. Select the truck with the highest ERTV, assign it to the recorded optimal trip once, and decide the starting time of the loading operation as early as possible according to both the expected truck arriving time and the involved shovel available time. Compute the complete times of both the truck and the shovel in the assigned round trip.Delete the truck fromS
idle. If the obtained trip complete time is in the given horizon, append the involved assignation and temporal information of truck, shovel, and dump to T
truck, T
shovel, and T
dump, respectively, and append the truck to S
running.Go to StepA
2.Step A4. If S
running
≠
∅, select a truck of the earliest trip complete time from S
running, delete the truck from S
running, and append it to S
idle; otherwise, output the current T
truck, T
shovel, and T
dump and stop.The above heuristic virtually simulates the equipment running process, especially the truck operation, and thus can be called a simulation-based solution construction approach. It is also appropriate to the online scheduling scene through displacing the above simulation process with the real production process.


### 4.2. Two Improvement Strategies

Through observation on the properties and upper bounds as well as analyzing the above heuristic method, two improvement strategies are proposed to improve the initial solution.Strategy 1 (the shovel capacity rebalancing strategy).
Strategy1 will refer to the defined shovel sequence i
1
,
i
2
,
…
,
i
N in the descending order of E
i
* (see Section 3.3). Because the initial truck position can be far away from the shovel with higher E
i
*, the strategy should reassign more trucks to these shovels for the objective pursuit.
Steps of Strategy1 are listed as follows.
Step B1. Let n
=
1 and current shovel i
*
=
i
n.
Step B2. Check the shovel dispatch information table T
shovel in the current solution and compute the total idle times of shovel i
* after finishing its first truck loading. Let t
idle denote the computed idle times and let S
remained denote the set of trucks assigned to shoveli
n
+
1
,
i
n
+
2
,
…
,
i
N.
Step B3. If t
idle
/
p
i
0
≥
μ
H
/
P
i
*
*, in the beginning, reassign t
idle
P
i
*
*
/
μ
p
i
0
H trucks to shovel i
* from S
remained, reschedule the scheduled total truck routine through repeating Steps (
A
2
–A
4
) in the initial solution approach, and delete these reassigned trucks from truck set S
remained. Note that trucks with lower ERTV should be given priority to be reassigned.
Step B4. If S
remained
≠
∅, set n
=
n
+
1, i
*
=
i
n, and go to Step B
2; otherwise, terminate.Strategy 2 (neighborhood swapping strategy).
Strategy2 is a simple neighborhood swapping strategy. It includes the following steps.
Step C1. Set truck set S
remained
=
T. Let t denote any truck in S
remained and delete t from S
remained.
Step C2. Let r
1
,
r
2
,
…
,
r
m denote the set of truck round trips executed by truck t.
Setk
=
1.
Step C3. Attempt to reassign truck round trip r
k to other shovels and revise the involved truck schedule. If there is a reassignment that can bring an improvement, accept the alteration.
Step C4. If k
<
m, set k
=
k
+
1 and go to Step C
3.
Step C5. If S
remained
≠
∅, take a new truck t from S
remained and return to Step C
2; otherwise, terminate.


## 4.1. A Constructive Heuristic Method to Generate Initial Solution

In the practical scheduling process, truck waiting times are often inevitable and thus the conception of expected real-time transport value is introduced here.Definition 4.
In the practical truck scheduling,e
j
i
j
′
*
=
a
i
/
(
P
j
i
0
+
P
i
j
′
1
+
p
i
0
+
p
j
1
+
δ
), j
,
i
,
j
′, j
∈
D, j
′
∈
D
i, i
∈
S,  is called expected real-time transport value (ERTV) for a possible truck round trip selection, where δ is the expected truck waiting time (invaluable truck times) during the whole trip.Based on the above definition, a constructive heuristic method can be introduced to generate the initial solution. It includes the following steps.Step A1. Build a truck set S
idle, including all trucks that are not assigned to a round trip or just finished a round trip in the scheduling, and set S
idle to include all trucks in the initial state.Build a truck setS
running and let S
running
=
∅ in the initial state.Build a truck scheduling information tableT
truck, a shovel dispatch information table T
shovel, and a dump scheduling information table T
dump. Initialize the three information tables with T
truck
=
∅, T
shovel
=
∅, and T
dump
=
∅.Step A2. If S
idle
≠
∅, for each truck in S
idle, construct the corresponding round trips, compute their expected real-time transport values in the current state (referring to T
truck, T
shovel, and T
dump), and record the trip with the highest ERTV and its ERTV; otherwise, go to Step A
4.Step A3. Select the truck with the highest ERTV, assign it to the recorded optimal trip once, and decide the starting time of the loading operation as early as possible according to both the expected truck arriving time and the involved shovel available time. Compute the complete times of both the truck and the shovel in the assigned round trip.Delete the truck fromS
idle. If the obtained trip complete time is in the given horizon, append the involved assignation and temporal information of truck, shovel, and dump to T
truck, T
shovel, and T
dump, respectively, and append the truck to S
running.Go to StepA
2.Step A4. If S
running
≠
∅, select a truck of the earliest trip complete time from S
running, delete the truck from S
running, and append it to S
idle; otherwise, output the current T
truck, T
shovel, and T
dump and stop.The above heuristic virtually simulates the equipment running process, especially the truck operation, and thus can be called a simulation-based solution construction approach. It is also appropriate to the online scheduling scene through displacing the above simulation process with the real production process.


## 4.2. Two Improvement Strategies

Through observation on the properties and upper bounds as well as analyzing the above heuristic method, two improvement strategies are proposed to improve the initial solution.Strategy 1 (the shovel capacity rebalancing strategy).
Strategy1 will refer to the defined shovel sequence i
1
,
i
2
,
…
,
i
N in the descending order of E
i
* (see Section 3.3). Because the initial truck position can be far away from the shovel with higher E
i
*, the strategy should reassign more trucks to these shovels for the objective pursuit.
Steps of Strategy1 are listed as follows.
Step B1. Let n
=
1 and current shovel i
*
=
i
n.
Step B2. Check the shovel dispatch information table T
shovel in the current solution and compute the total idle times of shovel i
* after finishing its first truck loading. Let t
idle denote the computed idle times and let S
remained denote the set of trucks assigned to shoveli
n
+
1
,
i
n
+
2
,
…
,
i
N.
Step B3. If t
idle
/
p
i
0
≥
μ
H
/
P
i
*
*, in the beginning, reassign t
idle
P
i
*
*
/
μ
p
i
0
H trucks to shovel i
* from S
remained, reschedule the scheduled total truck routine through repeating Steps (
A
2
–A
4
) in the initial solution approach, and delete these reassigned trucks from truck set S
remained. Note that trucks with lower ERTV should be given priority to be reassigned.
Step B4. If S
remained
≠
∅, set n
=
n
+
1, i
*
=
i
n, and go to Step B
2; otherwise, terminate.Strategy 2 (neighborhood swapping strategy).
Strategy2 is a simple neighborhood swapping strategy. It includes the following steps.
Step C1. Set truck set S
remained
=
T. Let t denote any truck in S
remained and delete t from S
remained.
Step C2. Let r
1
,
r
2
,
…
,
r
m denote the set of truck round trips executed by truck t.
Setk
=
1.
Step C3. Attempt to reassign truck round trip r
k to other shovels and revise the involved truck schedule. If there is a reassignment that can bring an improvement, accept the alteration.
Step C4. If k
<
m, set k
=
k
+
1 and go to Step C
3.
Step C5. If S
remained
≠
∅, take a new truck t from S
remained and return to Step C
2; otherwise, terminate.


## 5. Computational Experiments

To test the performance of the formulated mathematic model and the proposed heuristic approach with improvement strategies, we complemented all the involved programs under the development environment of VC++ 2010 and solved the integer programming model in Section2 with CPLEX, a kind of optimization software. The experiments are all performed on a computer with Win 7 operating system and 2.8 GHz Intel 2 Core CPU and 4 GB RAM.The data in the numerical experiments comes from a practical open-pit mine. The data includes 8 problem instances but involves only 2 different mine path configurations due to the relative constancy of the open-pit road network. Table1 shows the details of the problem instances, including path configuration (Path), problem instance ID (Problem), number of trucks (Trucks), number of shovels (Shovels), and number of dumps (Dumps). The scheduling horizon is a shift, 8 hours, for all instances.Table 1
Parameters of the problem instances.
Path
Problem
Trucks
Shovels
Dumps
1
1
73
6
3
2
71
6
3
3
74
6
3
4
69
6
3
2
5
84
6
4
6
82
6
4
7
85
6
4
8
85
6
4The transport revenue per truck of material is product of the expected shortest distance and the priority factor of the loading point. The priority factor ranges in[
0.9,1.1
] in the production scheduling. In the truck-shovel system, the truck capacity is usually scarce for the loading capacity of shovels. All these features are also reflected in the collected problem instances.The small sized problems are first solved using the formulated mathematic models (with CPLEX) and the proposed heuristic approach. The small sized problem instances are cut out from instances of path configurations 1 and 2 in Table1 and the scheduling horizon is decreased to 2 hours. Each of the small sized problem instances involves 2 shovels, 2 dumps, and different number of available trucks. Table 2 shows the experiment results with the different problem sizes (number of available trucks). In the table, columns Path and Size show the path configuration and number of available trucks, respectively. Models Model_Ineq and Heu_Imp represent the mathematical model, model with inequalities (17)–(19), and the heuristic with improvement strategy, respectively.Table 2
Experiment result for the small sized problems.
Path
Size
Objective value
CPU time (seconds)
Model
Heu
Model
Model_InEq
Heu_Imp
1
3
5.4
5.4
4.37
4.46
<1
2
3
5.8
5.8
9.61
7.84
<1
1
6
11.1
11.1
37.14
24.83
<1
2
6
11.8
11.8
41.90
34.09
<1
1
9
16.9
16.9
173.48
113.87
<1
2
9
17.7
17.7
143.34
86.17
<1
1
12
22.6
22.0
479.55
454.84
<1
2
12
23.4
23.4
513.63
494.56
<1The experiment results of the practical problem instances are listed in Table3 with problem ID (Problem), objective values of the initial solution (Heuristic), and improved solution (Improvement), which are improved by the developed two improvement strategies, relative improvement (Relative imp.), best upper bound (UB), which adopts the maximum of two upper bounds in Section 3.3, and the relative deviation of the obtained optimized solution and the upper bound. The computation times for all instances are not longer than 5 CPU seconds and thus neglected in the table.Table 3
Experiment result and comparison for the practical problem size.
Problem
Objective value
Relative imp.
UB
GAP
Heuristic
Improvement
1
543
551
1.58%
585
5.70%
2
536
543
1.26%
559
2.96%
3
569
578
1.61%
601
3.80%
4
509
534
4.68%
558
4.36%
5
637
659
3.34%
697
5.46%
6
588
619
5.05%
650
4.79%
7
652
667
2.34%
705
5.40%
8
661
691
4.34%
714
3.19%
Average
—
—
3.02%
—
4.46%From Table2, we can see that the mathematical model is valid but not up to the practical problem size. From Table 3, we can observe that the average relative deviation is 4.46% and the two improvement strategies perform 3.02% increase on average. The experiments show that the proposed upper bound is good and the developed heuristic solution approach with improvement strategies is effective and efficient. And the solution performance is relatively stable against different problem configurations.


## 6. Conclusion

In this paper, a special open-pit truck scheduling problem was studied. A mixed integer programming model was first formulated, considering transport revenue varied with different loading points. And a few valid inequalities, two properties, and two upper bounds of the problem were deduced. Based on them, a heuristic solution approach with two improvement strategies was proposed to resolve the problem. At last, the numerical experiments were carried out which demonstrated that the proposed solution approach was effective and efficient.



---

*Source: 745378-2015-03-18.xml*