Sage Journals: Discover world-class research

Abstract

Given dynamic variations in the scheduling environment for ready-mixed concrete vehicles, an advance schedule should be able to accommodate such changes. The authors studied the rescheduling characteristics of ready-mixed concrete vehicle fleet operations and measured the dynamics of randomly arriving customers’ requirements. Based on the study’s findings, a corresponding rescheduling strategy and a hybrid heuristic algorithm are proposed to optimize the rescheduling system for such vehicles. The simulation results validated the model and proved the effectiveness of the rescheduling strategy and the hybrid heuristic algorithm regarding the optimization of the rescheduling of ready-mixed concrete vehicles.

Keywords

Ready-mixed concrete vehicle scheduling problem rescheduling heuristic algorithm genetic algorithm

Introduction

The scheduling of ready-mixed concrete vehicles (RMCVs) is a complex combinatorial optimization problem that includes vehicle sequencing, loading sequencing at the mixing plant, time-pressure from the construction industry, and just-in-time manufacturing issues. Because of transportation uncertainties, random delivery times and quantities, dynamic emergence of new customer demands, and other problems such as vehicle malfunctions, mixing plant malfunctions, pump malfunctions, and weather variations, the scheduling environment for RMCVs is dynamic.¹ To respond to these dynamic factors, rescheduling of RMCVs is important because otherwise, formulated plans may be delayed. This study focuses on the dynamics of random customers’ requirements and proposes a corresponding rescheduling strategy and a heuristic genetic algorithm (GA) to optimize it.

The RMCV scheduling problem can be viewed as a type of special truck and trailer routing problem (TTRP), among the most widely studied and important combinatorial optimization problems in the field of vehicle routing problems (VRPs). There exist many works on the stochastic demand for VRP and TTRP, along with the reviews of the same.^2–9 The RMCV scheduling problem is different from VRP and TTRP because it includes not only time window constraints, timely placement constraints, and productivity limits but also RMCV limitations in that only one customer can be served per operation and in that each customer’s demand is to be satisfied sequentially.

Tommelein and Li¹⁰ analyzed the production and delivery characteristics of the RMCV scheduling problem and indicated that it belonged to a special class of supply-chain management problems. Matsatsinis¹¹ reported that a special pumping device was needed to assist the unloading of concrete at the construction site and established the decision support system for RMC scheduling. Feng et al.^12,13 constructed a simulation model for the scheduling of RMCVs in a single depot and used a generic algorithm to optimize the problem instances. Naso et al.¹⁴ built a nonlinear programming model for the scheduling of RMCVs in multiple mixing plants and employed a two-phase algorithm to optimize the model. Yan et al.^15–18 established an edge-constrained hydride integer network flow model for the scheduling of RMCVs by integrating the production sequence and vehicle scheduling sequence of the mixing plant into one network flow model. Asbach et al.¹⁹ built a hydride integer planning model for RMCV scheduling using network flows and optimized the instances using neighborhood search. Schmid expanded the classical VRP and established an integer multi-commodity network flow model for the scheduling of the RMC integer. In addition, he optimized the concrete scheduling instances using a deterministic algorithm and variable neighborhood search.^20–22

However, the above-mentioned studies only assess static scheduling. Durbin and Hoffman¹ employed a local time-horizon model to treat the dynamic variations in customer demand. However, the size of the time-horizon had much influence on the scheduling effect in his model: a small time-horizon yields an unfeasible albeit approximate optimal solution, while a large one postponed the consideration of dynamic events resulting in the low availability of the scheduling results. Thus, although many works do exist on rescheduling, this study proposed a rescheduling strategy and a hybrid heuristic algorithm to rapidly solve the RMCV scheduling problem in a dynamic environment.^22–24

The rest of this article is organized as follows. Section “RMCV scheduling problem” proposes the model used for scheduling RMCVs. Section “Rescheduling strategy for RMCVs” measures the dynamic level of customer demand and presents a rescheduling strategy for RMCVs. Section “Hybrid GA” details the heuristic GA, and section “Empirical verification using real data” evaluates the same via an application. Section “Conclusion” concludes the article.

RMCV scheduling problem

At the start time of scheduling, there is a depot denoted by D, which has a vehicle fleet $K = {K_{1}, \dots, K_{r}}$ for delivering concrete to customers. All vehicles in K can only load RMC and have the same loading capacity $q (K)$ ; on a given working day, each vehicle starts its journey at the depot and has to return to the depot at the end of the working day. When generating vehicle schedules, $Rt (k)$ represents a moment $k \in K$ when the vehicle can be used. Then, there are sets $C = {C_{1}, \dots, C_{n}}$ of n customers, each customer having a positive demand for concrete, $q (c) \in Q^{+}$ . If the full demand $q (c)$ of customer c is not satisfied, penalty costs $β_{1} \in R$ and $β_{2} \in R$ are applied; $β_{1}$ refers to the punishment when customer demand is not fully met, while $β_{2}$ is the punishment for the missing quantity of RMC that the customer needs. Furthermore, $β_{1} >> β_{2}$ , in that a customer’s demand is attempted to be fully met, but if this is not possible, then the most possible amount of concrete is delivered to the customer. The remaining demand can be met by other ways, such as outsourcing. This is expected to be investigated in the authors’ future research.

A vehicle that arrives at customer c requires service time $S (c)$ for services such as parking and unloading. A delivery vehicle has to begin supplying customer c within the hard time window $[a (c), b (c)]$ . The customer is also likely to specify a first delivery deadline $b' (c)$ , which means that the first delivery of the day must start within the time interval $[a (c), b' (c)]$ . Furthermore, the customer specifies two time intervals $mintl (c) \in N$ and $maxtl (c) \in N$ in which deliveries need to be made. If a subset of the vehicle fleet conducts a set of $n_{c}$ deliveries to customer c, he or she is supplied at chronological times $w_{1}, w_{2}, \dots, w_{n_{c}}$ . A minimum time lag $mintl (c)$ and a maximum time lag $maxtl (c)$ enforce two consecutive deliveries $i, i + 1$ to a customer, which are neither too far nor too close in time, that is, $mintl (c) ⩽ w_{i + 1} - w_{i} ⩽ maxtl (c)$ , where $i \in {i, \dots, n - 1}$ .

Depot D also has a service time $S (D) \in N$ for services such as parking the vehicles and filling them. Given the limited production rate of depot D, a minimum time lag $mintl (D) \in N$ ensures that two consecutive loading operations at the depot are not too close in time. Furthermore, a time window $[a (D), b (D)]$ assigned to the depot restricts the time of reloading. The cost of delivering concrete using an RMC vehicle during the working day is denoted by $α (K) \in R$ . Owing to the perishable nature of concrete, the maximum time that concrete may reside in the vehicles is represented by parameter $γ \in N$ .

Mathematical model

Using the parameters given in the previous section and on the basis of a mixed integer programming model, a network flow model G is defined. In the model, each possible delivery is conducted to a customer, and each possible reload at the depot, the starting point, and the ending point of the RMCV are presented as individual nodes. Graph $G = (V, E, t, Z)$ is demonstrated as follows.

Depot D is represented by $D^{G} = {D_{1}, \dots, D_{n (D)}}$ . Each $D_{i}$ is a possible reloading at the depot, where $n (D) = (b (D) - a (D)) / mintl (D)$ is the maximum number of possible reloadings of vehicles at the depot during the considered working day. Analogously, this study represents every customer $C_{i} \in C$ in the model by $C_{i}^{G} = {C_{i, 1}, \dots, C_{i, n (C_{i})}}$ customer nodes, where $n (C_{i}) = q (C_{i}) / q (K)$ is the maximum number of necessary deliveries to $C_{i}$ . The node set V of G is defined as $V = C^{G} \cup D^{G} \cup S \cup P$ , where $C^{G} = \sum_{i = 1}^{n} C_{i}^{G}$ , S represents the artificial starting node and P the artificial ending node. Edge set E of G is defined as $(u, v, k)$ , where $u \in V, v \in V, k \in K$ . In graph G, $t : (C^{G} \cup D^{G} \cup S \cup P) \times (C^{G} \cup D^{G} \cup S \cup P)$ is the time used by the vehicle to travel across the edge of E, where × is the symbol representing the Cartesian product. Furthermore, $Z : (C^{G} \cup D^{G} \cup S \cup P) \times (C^{G} \cup D^{G} \cup S \cup P)$ is the cost of the edge. In the model, the vehicles are of the same loading capacity, and as such, the cost and the transportation time for an edge are independent of the vehicles. Accordingly, $(u, v, k)$ is simplified to $(u, v)$ . Since there are various kinds of edges, it is important to identify and consider only the edges feasible for scheduling.

For example, $(u, v) \in S \times C^{G}$ and $(u, v) \in C^{G} \times C^{G}$ , as two kinds of edges, represent a vehicle’s travel from the starting node to a customer node and from a customer node to another, respectively. It is obvious that concrete must have been loaded in vehicles prior to delivery to customers. The customer-specific nature of concrete implies that a vehicle cannot service two customers in the same round. Therefore, these two kinds of edges should be removed.

Furthermore, $(u, v) \in D^{G} \times D^{G}$ and $(u, v) \in D^{G} \times P$ , as two kinds of edges, denote a vehicle’s travel from a depot node to another or to the ending node, respectively. Because vehicles have to service customers after being loaded, these two kinds of edges too should be removed.

Edge $(u, v) \in (C^{G} \cup D^{G} \cup P) \times S$ implies that the vehicles have reached the starting node, and $(u, v) \in P \times (C^{G} \cup D^{G} \cup S)$ indicates that the vehicles have started from the ending node. Apparently, these two kinds of edges should be removed.

The remaining types of edges that are fit for scheduling are kept in the model and are described as follows.

Edges of type $(u, v) \in S \times D^{G}$ represent the starting time of the vehicle’s service for a customer; that is, it refers to the first loading operation of the day. In the model, all vehicles come back to the depot after finishing their jobs for the day, and thus, the time used in this case is 0 (i.e. $t (u, v) = 0$ ) and the cost $Z (u, v) = α (K)$ of the edge is the cost of using the vehicle for delivering concrete during the working day.

$(u, v) \in S \times P$ represents the vehicles going directly from the starting node to the ending node and have thus not been used in the working day. Hence, such an edge involves no travel time or cost.

$(u, v) \in D^{G} \times C^{G}$ and $(u, v) \in C^{G} \times D^{G}$ represent vehicles reloading in the depot for servicing a customer and those that have finished unloading at a customer node and are returning to a depot for another reloading, respectively. By combining these two types of edges, the time spent for delivering concrete to a customer or for the return trip from a customer to a depot is derived. This time function is represented by $t (u, v) = dis (u, v) / Vspeed$ , where $dis (u, v)$ is the distance between nodes u and v and Vspeed is the vehicle speed during the travel, which is assumed to be constant in this article. Furthermore, $Z (u, v) = p \cdot t (u, v) + q \cdot (w_{v} - w_{u} - t (u, v))$ is the cost of an edge, where p is the transportation cost per unit time, $w_{u}$ is the time taken for vehicle loading at the depot or for unloading at a construction site, and $w_{v}$ is the time at which the vehicle arrivals at node v.

$(u, v) \in C^{G} \times P$ is the vehicles’ last unloading operation of the working day. The time function indicates the travel time of the vehicle’s return to the depot from the construction site, and the cost function stands for the incurred transportation expense. Using the network flow models mentioned above, a mixed integer programming model for solving the RMCV scheduling problem is constructed. The decision variables of the model are

\begin{matrix} x_{uvk} = {\begin{matrix} 1, if there is a truck k from node u to v \\ 0, otherwise \end{matrix} \\ w_{u} = {\begin{matrix} T, time at which vehicle k reached u, \forall (u, v, k) \in E, x_{u, v, k} = 1 \\ \emptyset, \forall (u, v, k) \in E, x_{u, v, k} = 0 \end{matrix} \\ y_{c} = {\begin{matrix} 1, if the total demand q (c) of customer c is satisfied, \forall c \in C \\ 0, otherwise \end{matrix} \end{matrix}

To simplify notation, the article defines two sets: $Δ^{+} (u) : {v | (u, v, k) \in E}$ of node $u \in V$ as the subsequent nodes of u with respect to graph G, and $Δ^{-} (u) : {v | (u, v, k) \in E}$ of node $u \in V$ as the precursor nodes of u. The detailed equations of this model are as follows

Min \sum_{(u, v, k) \in E} x_{uvk} \cdot Z (u, v) + \sum_{c \in C} [q' (c) \cdot β_{2} + (1 - y_{c}) \cdot β_{1}]

(1)

\sum_{(u, v, k) \in E} x_{uvk} \cdot w_{u} > Rt (k)

(2)

\sum_{v \in Δ^{+} (S)} x_{Svk} = 1

(3)

\sum_{u \in Δ^{-} (E)} x_{uEk} = 1

(4)

\sum_{u \in Δ^{-} (v)} x_{uvk} - \sum_{u \in Δ^{+} (v)} x_{uvk} = 0 \forall v \in C^{G} \cup D^{G}, \forall k \in K

(5)

\sum_{k \in K} \sum_{v \in Δ^{+} (u)} x_{uvk} ⩽ 1 \forall u \in C^{G}

(6)

\sum_{k \in K} \sum_{v \in Δ^{+} (u)} x_{uvk} ⩽ 1 \forall u \in D^{G}

(7)

\begin{array}{l} \sum_{k \in K} \sum_{v \in Δ^{+} (C_{i, j + 1})} x_{C_{i, j + 1} v k} - \sum_{k \in K} \sum_{v \in Δ^{+} (C_{i, j})} x_{C_{i, j} v k} ⩽ 0 \\ \forall i \in {1, \dots, n}, \forall j \in {1, \dots, n (C_{i}) - 1} \end{array}

(8)

\begin{array}{l} q (C_{i}) - \sum_{k \in K} \sum_{u \in C_{i}^{G}} \sum_{v \in Δ^{+} (u)} x_{u v k} \cdot q (k) = q^{'} (C_{i}) \\ \forall i \in {1, \dots, n}, \forall j \in {1, \dots, n (C_{i}) - 1} \end{array}

(9)

\sum_{k \in K} \sum_{u \in C_{i}^{G}} \sum_{v \in Δ^{+} (u)} x_{uvk} \cdot q (k) ⩾ q (C_{i}) \cdot y_{C_{i}} \forall i \in {1, \dots, n}

(10)

- M \cdot (1 - x_{u v k}) + S (u) + t (u, v) ⩽ w_{v} - w_{u} \forall (u, v, k) \in E

(11)

\begin{array}{l} M \cdot (1 - x_{u v k}) + γ + S (u) ⩾ w_{v} - w_{u} \\ \forall (u, v, k) \in E with u \in D^{G}, v \in C^{G} \end{array}

(12)

w_{u} ⩾ a (u) \forall u \in C^{G} \cup D^{G}

(13)

w_{u} ⩽ b (u) \forall u \in C^{G} \cup D^{G}

(14)

w_{C_{i, 1}} ⩽ b' (u) \forall i \in {1, \dots, n}

(15)

\begin{array}{l} w_{C_{i, j + 1}} - w_{C_{i, j}} ⩾ m i n t l (C_{i}) \\ \forall i \in {1, \dots, n}, \forall j \in {1, \dots, n (C_{i}) - 1} \end{array}

(16)

\begin{array}{l} w_{C_{i, j + 1}} - w_{C_{i, j}} ⩽ m a x t l (C_{i}) \\ \forall i \in {1, \dots, n}, \forall j \in {1, \dots, n (C_{i}) - 1} \end{array}

(17)

w_{D_{i + 1}} - w_{D_{i}} ⩾ mintl (D) \forall j \in {1, \dots, n (D) - 1}

(18)

x_{uvk} \in {0, 1} \forall (u, v, k) \in E

(19)

w_{u} \in T \forall u \in C^{G} \cup D^{G}

(20)

y_{c} \in {0, 1} \forall c \in C

(21)

Objective function (1) minimizes the total sum of the costs of the edges applied by a random vehicle so that through penalty costs $β_{1}$ and $β_{2}$ , the most frequent concrete delivery possible is ensured to the customers. Constraint (2) demonstrates that the availability time of a vehicle must precede the time when the vehicle starts working. Constraints (3) and (4) demonstrate that each vehicle can depart from the starting node and reach the ending node only once. Constraint (5) conserves the flow for all nodes except the technical starting and ending nodes. Constraint (6) is used to ensure that each customer node is employed at most once. Constraint (7) states that the depot can load only one vehicle at a time. Constraint (8) confirms that a customer’s demand must be satisfied sequentially. Then, given a vehicle supplying a customer node $C_{ij}$ , no vehicle supplies customer node $C_{ij'}$ with $j' > j$ . Equation (9) is used to calculate the remaining demand of an unsatisfied customer. In constraint (10), $y_{c}$ indicates whether the customer cs is satisfied. Constraint (11) ensures that a vehicle from node u to node v complies with the time constraints using a large constant M: x and w are related given the enforcement of travel times and service times. Constraint (12) is used to ensure that no concrete is kept in the mixer for more than $γ$ units of time. Constraints (13) and (14) ensure that the time windows are respected. Constrain (15) enforces the first delivery to a customer given deadline $b' (c)$ . Two consecutive deliveries for a customer must abide by the time lag constraints (16) and (17). Constraints (18) and (7) restrict depot productivity. Finally, constraints (19)–(21) define the domains of the decision variables.

Rescheduling strategy for RMCVs

Any baseline plan for RMCVs would be unfeasible under customers’ dynamic demands, as shown in Figure 1. The dynamic needs of customers would lead to rescheduling. To consider this, first, the level of dynamic demands of customers given the status of the scheduling system at the time is measured, and then, the time at which the rescheduling operation needs to be executed is calculated using the parameters of the dynamic level, such as the average execution time of the algorithm.

Figure 1.

Example of the RMCV rescheduling problem.

Status of the scheduling system at time $T_{t}$

Before rescheduling, the state of the scheduling system at that time needs to be assessed. The state of scheduling system at time $T_{t}$ is represented by a triplet $Sta (T_{t}) = 〈 VS (T_{t}), CS (T_{t}), DS (T_{t}) 〉$ , where $VS (T_{t}) = 〈 k, Rt (k) 〉$ is the state of vehicles at time $T_{t}$ , $Rt (k)$ represents the moment when vehicle $k \in K$ can be used after time $T_{t}$ , $CS (T_{t}) = 〈 C_{i}, q (C_{i}), [S_{t} (C_{i}), E_{t} (C_{i})] 〉$ is the state of customers at time $T_{t}$ , and $DS (T_{t}) = 〈 T_{up} 〉$ is the state of depot D at time $T_{t}$ .

The state of vehicles is represented by $VS (T_{t}) = 〈 k, Rt (k) 〉$ , where k refers to the vehicle used, and $Rt (k)$ represents the moment when vehicle $k \in K$ can be used after time $T_{t}$ . Only when $Rt (k)$ is known, operations can be assigned to vehicle k. At a given time $T_{t}$ , there are five cases of a vehicle’s position, as shown in Figure 2 and as described below:

Case 1: the vehicle is idle and is waiting at the depot.

Case 2: the vehicle is loading concrete at the depot.

Case 3: the vehicle is traveling to a customer.

Case 4: the vehicle is unloading at a construction site.

Case 5: the vehicle has finished an operation for a customer and is traveling to the depot for the next operation.

Figure 2.

Possible positions of a vehicle.

To determine the time of availability for each vehicle in the rescheduling process, it is first necessary to determine which customers were served by the vehicle before $T_{t}$ . Equation (22) equals 1 refers to the vehicles that start off to serve customers before $T_{t}$ , where $R t_{i} (k) = w_{v} + S (v) + dis (v) / Vspeed$ with subscript i denotes the return time of the ith operation of vehicle k before $T_{t}$ ; if otherwise, equation (22) equals −1. Therefore, at time $T_{t}$ , the time of availability of vehicle k in the rescheduling plan is $Rt (k) = \max {R t_{1} (k), \dots, R t_{i} (k), \dots, R t_{n} (k)}$ . The scheduling time of the baseline plan is represented as $T_{0}$ , and the vehicle state at time $T_{0}$ is $VS (T_{0}) = 〈 k, 0 〉$ . In other words, all vehicles are directly available at the initial state

\frac{x_{uvk} \cdot (T_{t} - w_{u})}{| w_{u} - T_{t} |} = {\begin{matrix} 1, \\ - 1, \end{matrix} \forall u \in D^{G}, x_{uvk} = 1

(22)

$CS (T_{t}) = 〈 C_{i}, q (C_{i}), [S_{t} (C_{i}), E_{t} (C_{i})] 〉$ refers to the customer state at time $T_{t}$ , where $C_{i}$ is the ith customer and $q (C_{i})$ is the concrete quantity needed by customer $C_{i}$ after $T_{t}$ ; $[S_{t} (C_{i}), E_{t} (C_{i})]$ is the starting time window of the operation needed to be scheduled for customer $C_{i}$ at some time after $T_{t}$ . For an arbitrary customer, the concrete quantity needed by customer $C_{i}$ at $T_{t}$ is found from equation (23), where $\bar{q} (C_{i})$ is the quantity of concrete needed by customer $C_{i}$ in the last time period; the starting time window needed to be scheduled for each customer can be determined by equations (24) and (25); and J is the number of operations needed by the customer. At $T_{t}$ , the starting time window of customer $C_{i}$ in the rescheduling plan is $[a (C_{i}), b (C_{i})] = [S_{t} (C_{i}), E_{t} (C_{i})]$ . At time point $T_{0}$ , the initial state of a customer is $CS (T_{0}) = 〈 C_{i}, q (C_{i}), [a (C_{i}), b (C_{i})] 〉$

\begin{array}{l} q (C_{i}) = \bar{q} (C_{i}) - \sum_{k \in K} \sum_{u \in Δ^{-} (v)} \sum_{v \in C_{i}^{G}} x_{u v k} \cdot q (k) \\ \forall v \in C_{i}^{G}, \sum_{k \in K} \sum_{u \in Δ^{-} (v)} x_{u v k} \cdot w_{u} < T_{t} \end{array}

(23)

S_{t} (C_{i}) = w_{C_{i, (n (C_{i}) - J)}} + S (C_{i}) + m i n t l (C_{i}) \forall C_{i} \in C, J = \frac{q (C_{i})}{q (k)}

(24)

E_{t} (C_{i}) = w_{C_{i, (n (C_{i}) - J)}} + S (C_{i}) + m a x t l (C_{i}) \forall C_{i} \in C, J = \frac{q (C_{i})}{q (k)}

(25)

In any system state, $DS (T_{t}) = 〈 T_{up} 〉$ is the state of the mixing plant at $T_{t}$ , with $T_{up}$ being the current rescheduling time point. In this study, any possible loading in the mixing plant would be integrated into the networking flow model as a node. Therefore, rescheduling at an arbitrary $T_{t}$ , the available mixing plant nodes in figure G are $D^{G} = {D_{1}, \dots, D_{T_{t} (D)}}$ , where $T_{t} (D) = (b (D) - T_{up}) / mintl (D)$ . At time $T_{0}$ , the initial state of the mixing plant was $DS (T_{0}) = 〈 a (D) 〉$ .

Measuring the dynamic level

Customers’ dynamic random demands involve two aspects: quantity of concrete and delivery time. If the scheduled time slot is very small, rescheduling needs to be executed in a timely manner; otherwise, it can be slowed until more dynamic demand arrives. When the change in quantity is large, a timely adjustment of the original scheduling plan is likely to be effective in saving operating costs; for example, if a customer cancels many deliveries, the number of vehicles used in the original schedule can be reduced by timely rescheduling. Before the imposition of dynamic demand, it is necessary to measure the dynamic level of this demand and determine the rescheduling method requirements according to the dynamic level so as to minimize the effects on the original plan.

Dynamic demand, across all types, contains a starting time window. If dynamic demand cancels r operations, the starting time window for this dynamic demand is directly calculated as $a (C_{i}) = w_{C_{i, (n (C_{i}) - r)}} + S (C_{i}) + mintl (C_{i}), b' (C_{i}) = w_{C_{i, (n (C_{i}) - r)}} + S (C_{i}) + maxtl (C_{i})$ by using the original scheduling plan. If dynamic demand increases r operations, the staring time window is $a (C_{i}) = w_{C_{i, (n (C_{i}))}} + S (C_{i}) + mintl (C_{i}), b' (C_{i}) = w_{C_{i, (n (C_{i}))}} + S (C_{i}) + maxtl (C_{i})$ . If dynamic demand is from the entry of a new customer, the starting time window is specified as $[a (C_{i}), b' (C_{i})]$ . In what follows, the dynamic levels for each scenario are determined.

The level of dynamic random demand is decided by two aspects. One is the level of available depot nodes (noted as $AvailS (D)$ ) in the time window $[s t_{1} (C_{i}), s t_{2} (C_{i})]$ , which represents the latest lower bound for the first operation of customer $C_{i}$ (see equation (26)), where $a (C_{i})$ and $b' (C_{i})$ denote the start time window of customer $C_{i}$ given the state at that time, and $t (C_{i}, D)$ is the transportation time from the depot to customer $C_{i}$ . $AvailS (D)$ is the ratio of $Os (D)$ to $(s t_{2} (C_{i}) - s t_{1} (C_{i})) / mintl (D)$ (see equation (27)), where $Os (D)$ denotes the amount of assigned depot nodes in the original scheduling plan within time window $[s t_{1} (C_{i}), s t_{2} (C_{i})]$ , and $(s t_{2} (C_{i}) - s t_{1} (C_{i})) / mintl (D)$ is the largest depot node contained in time window $[s t_{1} (C_{i}), s t_{2} (C_{i})]$

[s t_{1} (C_{i}), s t_{2} (C_{i})] = [a (C_{i}) - t (C_{i}, D) - S (D), b^{'} (C_{i}) - t (C_{i}, D) - S (D)]

(26)

AvailS (D) = \frac{Os (D)}{(s t_{2} (C_{i}) - s t_{1} (C_{i})) / mintl (D)}

(27)

The other level of dynamic random demand (labeled $AvailA (D)$ ) is that of the available depot nodes in time window $[s t_{1} (C_{i}), et (C_{i})]$ . This time window represents the start time range for all operations of customer $C_{i}$ (see equation (28)), where $et (C_{i})$ is the latest start time of the last operation of customer $C_{i}$ . Larger values of $AvailA (D)$ imply that there are less available depot nodes in time range $[s t_{1} (C_{i}), et (C_{i})]$ , and contrary otherwise. In equation (29), $OA (D)$ represents the assigned depot nodes in the original scheduling plan within time window $[s t_{1} (C_{i}), et (C_{i})]$ , and $(et (C_{i}) - s t_{1} (C_{i})) / mintl (D)$ is the largest depot node contained in time window $[s t_{1} (C_{i}), et (C_{i})]$

[s t_{1} (C_{i}), et (C_{i})] = [s t_{1} (C_{i}), \frac{q (C_{i})}{q (k)} \cdot (S (C_{i}) + maxtl (C_{i}))]

(28)

AvailA (D) = 1 - \frac{OA (D)}{(et (C_{i}) - s t_{1} (C_{i})) / mintl (D)}

(29)

Given parameters $AvailS (D)$ and $AvailA (D)$ , we set the dynamic level of a new customer as $Dy (C_{i}) = [AvailS (D) + AvailA (D)] / 2$ , where ⌊·⌋ represents rounding down. The range of $AvailS (D)$ is $[0, 1]$ , which means that if a depot node can be found for the first operation of customer $C_{i}$ , then the value of $AvailS (D)$ is not considered in $Dy (C_{i})$ . This is because if there are available nodes for the first operation, these can be found by the algorithm proposed in this study. A larger value of $Dy (C_{i})$ implies that rescheduling should be executed earlier; otherwise, it can be postponed for more dynamic random customer demands so as to minimize the impact on the execution of the original plan.

Time to execute rescheduling

The time to execute rescheduling is decided by the state of the scheduling system and the dynamic level $Dy (C_{i})$ of random demands. The average execution time of the algorithm is $t_{c}$ , which is a piecewise function of the quantity demanded by all customers. The greater the number of customers required, the greater is the value of $t_{c}$ . When the scheduling system receives the first message of dynamic demand at time $T_{r}$ , it calculates time $T_{t 1}$ (see equation (30)). $T_{t 1}$ is the moment of time when rescheduling is done to accommodate this dynamic demand. $(s t_{2} (C_{i}) - t_{c})$ is the latest by which the rescheduling operation is executed; if the rescheduling operation is executed after this time, the vehicle for the first delivery of customer $C_{i}$ would be delayed. If another dynamic demand arrives before $T_{t 1}$ , time $T_{t 2}$ is calculated, and the rescheduling operation is executed at $\min {T_{t 1}, T_{t 2}}$

T_{t 1} = (s t_{2} (C_{i}) - t_{c}) - (s t_{2} (C_{i}) - t_{c} - T_{r}) \cdot Dy (C_{i})

(30)

For each customer $C_{i}$ , the earliest start time $a (C_{i})$ of unloading must satisfy inequality $T_{r} < a (C_{i}) - t (C_{i}, D) - t_{c}$ . This is because concrete must be delivered to customer $C_{i}$ on time under transportation and algorithm execution time constraints.

When generating the rescheduling plan, if there are n customers in the original scheduling plan, the available depot nodes and vehicles should be first assigned to these n customers and then to service other new customers. The rescheduling strategy is set so as to not affect the original customers, while looking for the best outcome for the new customers.

Hybrid GA

In this study, using the mixed integer programming model for RMCV scheduling, an improved GA comprising heuristic rules is proposed. In addition, the hash function search strategy is used to improve the execution efficiency of the GA, as shown below.

Algorithm 1.

Heuristic hybrid genetic algorithm.

Step 1	Set a hash function to include previous individuals.
Step 2	Initialize a population with $pop_size$ individuals based on heuristic rules.
Step 3	Update individuals by cross operation and mutation.
Step 4	Check the hash table to ensure whether the individual objective value has been calculated. If it has been calculated, pick the objective value from the hash table, and if not, calculate the individual’s objective value and update the hash table.
Step 5	Given the objective value, calculate every individual’s fitness as $fit = \max - value$ , where max is given.
Step 6	Choose $pop_size$ individuals to be the next generation by RouletteWhell and optimization reserved strategy.
Step 7	Repeat Steps 3−6 until the given cycle-index is accomplished.
Step 8	Return to the optimal individual and use it as the optimal solution.

Encoding rules

As the loading capacity of all RMCVs is the same, the jobs of each customer are fixed as $n (C_{i}) = q (C_{i}) / q (k)$ . The encoding length of GA is defined as twice that of the aggregate jobs of all customers (Figure 3). This is because the departure time of the vehicles from the depot and the arrival time to customer nodes need to be obtained.

Figure 3.

Encoding of the genetic algorithm.

In our study, the minimum unit of time is a minute, and thus, the codes have natural numbers. Each solution displays a vector $X = (w_{u 1}, w_{v 1}, w_{u 2}, w_{v 2}, \dots, w_{um}, w_{vm})$ , where m represents the aggregate jobs of all customers, $m = \sum_{i = 1}^{n} n (C_{i})$ ; $w_{ui}$ is the time when the RMCV starts loading at the depot; and $w_{vi}$ is the time when the RMCV starts unloading at the construction site. Because the production rate at the depot is limited, an interval larger than $mintl (D)$ is required in two successive loading operations at the depot. Most concrete suppliers adopt the overbooking operations strategy (i.e. the actual number of orders received is larger than the productive capacity of the depot).¹ Therefore, heuristic rules are used in this study to have the number of nodes of the depot as the maximum possible loading operations $n (D) = (b (D) - a (D)) / mintl (D)$ . This can be done within the working time. Each node $D_{i}$ of the depot corresponds to one loading time, representing a possible loading operation in the depot and the related time of start of loading. At any time, a pair of coding structure $(w_{ui}, w_{vi})$ can be simplified into $(D_{j}, w_{vi})$ . To express this more precisely, $w_{ui}$ is used to express node $D_{j}$ of the depot and the related start of loading time.

Initialization

In the coding structure, each job of every customer is expressed as a time pair $(w_{ui}, w_{vi})$ . In this study, a heuristic rule is used to generate the initial individuals to validate its feasibility. The steps for producing an individual are as follows:

Step 1: customers are sorted in a stochastic order as $(C_{p 1}, C_{p 2}, \dots, C_{pn})$ because different search orders can lead to different results during the subsequent steps of searching depot nodes for every job. In this order, pi indicates the position of customers. For example, the result of sorting three customers can be $3, 2, 1$ shown as $C_{p 1} = C_{3}, C_{p 2} = C_{2}, C_{p 3} = C_{1}$ .

Step 2: set $j = 1$ and initialize $w_{v}$ of customer $C_{pj}$ . First, initialize the first job’s start unloading time $w_{v 1}$ of this customer as a random value within time window $[a (C_{pj}), b' (C_{pj})]$ . The aim is to meet the start time window’s requirement of customer $C_{pj}$ . The remaining jobs’ unloading time $w_{v}$ of customer $C_{pj}$ is initialized using $w_{v, i + 1} = w_{v, i} + rand ([mintl (C_{pj}), maxtl (C_{pj})])$ .

Step 3: given the produced $w_{v, i}$ , nodes of the depot are searched for serving the jobs of customer $C_{pj}$ . Starting from the last job $w_{v, n (C_{pj})}$ of the customer, an unused depot node $w_{u, n (C_{pj})}$ closest to $w_{v, n (C_{pj})}$ in time and time pair ( $w_{u, n (C_{pj})}, w_{v, n (C_{pj})}$ ) is searched such that it satisfies transportation constraints in the proposed model for serving this job. Then, another depot node to serve job $n (C_{pj}) - 1$ of this customer is searched until every job of customer $C_{pj}$ has a relevant depot node. In the process of searching, if an arbitrary job of customer $C_{pj}$ fails to find a depot node for its service, the setting is $w_{u, n (C_{pj})} = \emptyset$ , $n (C_{pj}) = n (C_{pj}) - 1$ . Then, the above searching processes are repeated. This means that if $n (C_{pj})$ jobs of the customer cannot be fulfilled, the searching process is executed again for $n (C_{pj}) - 1$ jobs of the customer.

Step 4: to set $j = j + 1$ , repeat Steps 2 and 3 until all jobs of all customers are initialized.

Calculation of objective value

The objective value of the model consists of the total cost of transportation and the penalty for unfinished jobs. To cover the cost of transportation, many jobs are completed. In the process, vehicles that completely fulfill their corresponding jobs need to be identified. Thus, first, jobs are included in the vehicles’ flow and then, this inclusion is used to calculate the objective value, as follows:

Step 1: rank all jobs of all customers in the increasing order of $w_{u} : ((w_{u 1}, w_{v 1}), (w_{u 2}, w_{v 2}), \dots, (w_{um}, w_{vm}))$ .

Step 2: assign the first job to vehicle $k = vehicle 1$ . In accordance with the job order of Step 1, the first job $(w_{ui}, w_{vi})$ that has not been included in any sequential vehicle flow is identified. Then, job $(w_{ui}, w_{vi})$ is inserted into the flow of vehicle k, making it the first job that vehicle k should fulfill, denoted as $(w_{u (k, s)}, w_{v (k, s)})$ , where s indicates the current position of vehicle flow k. If there is no such job, then all jobs of the customers have been finished.

Step 3: start from position $i + 1$ of the order in Step 1, to search jobs that RMCV k can serve. It shows that starting from job $(w_{u (i + 1)}, w_{v (i + 1)})$ in the order in Step 1, a sequential search is conducted until job $(w_{uj}, w_{vj})$ is found that has not been inserted into any vehicle flow. Then, if time pair $(w_{v (k, s)}, w_{uj})$ does not satisfy the transportation constraints of the model, the search process continues to check job $(w_{u (j + 1)}, w_{v (j + 1)})$ ; otherwise, set $(w_{u (k, s + 1)}, w_{v (k, s + 1)}) = (w_{uj}, w_{vj})$ . The results indicate that RMCV k can return to the depot after completing the previous job in time and then deliver for job $(w_{uj}, w_{vj})$ . Then, $s = s + 1$ is set to continue to search a job for the next assignment of vehicle k until all jobs have been checked.

Step 4: to set $k = next vehicle$ , repeat Steps 2 and 3 until all flows of all RMCVs have been checked/amended.

Step 5: given all vehicle flows, the number of unfulfilled jobs is ascertained. Accordingly, the penalty value for unfinished jobs is derived. The flow of vehicle k is expressed by time sequence $(w_{u (k, 1)}, w_{v (k, 1)}), (w_{u (k, 2)}, w_{v (k, 2)}), \dots, (w_{u (k, \in)}, w_{v (k, \in)})$ , and the sequence is used for the calculation of the objective value.

Crossover operator

The crossover operator plays a vital role in the evolution process because it imitates the mating process of the GA where some of the genes of the two paired chromosomes are exchanged to generate a new individual. The designed crossover operation is described in the following:

Step 1: judge if individual $j = 1$ is needed to execute a crossover operation using crossover probability. If needed, go to Step 2; otherwise, go to Step 6.

Step 2: for each $w_{ui}$ in individual j, every individual in the population except individual j that can be used in the crossover operation is searched. The principle of searching is as follows. The relevant value of $w_{ui}$ in the searched individual (expressed as $w_{ue}$ ) is to be such that there is no $w_{ue}$ in individual j, $w_{u (i - 1)} < w_{ue}$ , and $w_{ue} < w_{u (i + 1)}$ . Meanwhile, time pair $(w_{ue}, w_{vi})$ has to meet transportation constraints.

Step 3: for each $w_{vi}$ in individual j, every individual except individual j that can be used in the crossover operation is searched in the population. The principle of searching is as follows. The relevant value of $w_{v}$ in searched individuals (expressed as $w_{ve}$ ) is to be such that $mintl (c) ⩽ w_{v (i + 1)} - w_{ve} ⩽ maxtl (c)$ and $mintl (c) ⩽ w_{ve} - w_{v (i - 1)} ⩽ maxtl (c)$ , while time pair $(w_{ue}, w_{vi})$ has to meet the transportation constraints.

Step 4: define a probability for each position of individual j, which is the inverse of the ratio between the number of searched individuals and population size. For example, if the number of searched individuals is 3 and population size is 10, the probability of position $w_{ui}$ of an individual would be $1 - 3 / 10 = 0.7$ . The purpose of this exercise is to use a population containing a few searched individuals in the crossover operation because of their high probability of generating more new individuals.

Step 5: for each position where $w_{u}$ and $w_{v}$ of individual j that contains searched individuals can be used to execute the crossover operation by the probability mentioned in Step 4, the crossover operation randomly chooses an individual y from the searched individuals, and the value at the corresponding position of individual j is replaced with the value of individual y.

Step 6: for $j = j + 1$ , Steps 1–5 are re-executed until j is equal to the population size.

Mutation operator

The mutation operator defines the local search ability of the evolution process and is able to avoid missing information using the operation of selection and crossover. Thus, it maintains the variety of the population. The designed mutation operation is detailed in the following:

Step 1: judge if individual $j = 1$ is needed to execute the mutation operation using mutation probability. If there is no need to execute, go to Step 5; otherwise, go to Step 2.

Step 2: the mutation position of individual j is assigned as a random integer in interval $[1, 2 m]$ . $m = \sum_{i = 1}^{n} n (C_{i})$ shows the number of jobs for all customers. There are two situations in the mutation position: the depot node and relevant time $w_{u}$ , and the customer node and time $w_{v}$ .

Step 3: when the mutation position is $w_{ui}$ , and assuming $w_{ui}$ is the first job of a customer, then $w_{ui}$ is changed into $w_{ue}$ , which is a random integer between the lower limit $(a (D) + w_{vi}) / mintl (D) - γ / mintl (D)$ and the upper limit $(a (D) + w_{vi}) / mintl (D) - (mintl (C_{i}) + t_{f}) / mintl (D)$ , where $(a (D) + w_{vi}) / mintl (D)$ is the closest depot node in time to the customer node $w_{vi}$ ; $γ / mintl (D)$ expresses the number of times the RMCV can be loaded at the depot in time interval $[0, γ]$ , and $(mintl (C_{i}) + t_{f}) / mintl (D)$ indicates the number of times the vehicle can be loaded at the depot within the interval of the minimum transportation time from the depot to the customer. If $w_{ui}$ is not the first job of a customer, $w_{ui}$ is equal to a random integer in $[w_{u (i - 1)}, w_{u (i + 1)}]$ and be expressed as $w_{ue}$ . When $w_{ui}$ of individual j equals $w_{ue}$ , it has to satisfy the fact that $w_{ue}$ has not appeared in individual j, and $w_{ue} > w_{u (i - 1)}$ ; meanwhile, time pair $(w_{ue}, w_{vi})$ has to meet transportation constraints.

Step 4: when the mutation position is $w_{vi}$ and if $w_{vi}$ is the first job of an arbitrary customer, $w_{vi}$ is equal to $w_{ve}$ , which is a random integer between $[a (C_{i}), b' (C_{i})]$ . If $w_{vi}$ is not the first job of the customer, $w_{vi}$ equals a random integer in $[w_{v (i - 1)}, w_{v (i + 1)}]$ , where the changed value is denoted as $w_{ve}$ . Then, $mintl (c) ⩽ w_{v (i + 1)} - w_{ve} ⩽ maxtl (c)$ and $mintl (c) ⩽ w_{ve} - w_{v (i - 1)} ⩽ maxtl (c)$ , and $(w_{ue}, w_{vi})$ has to meet the transportation constraints.

Step 5: for $j = j + 1$ , re-execute Steps 1–4 until j is equal to the population size.

Selection of operator

The selection of an operator involves the process of choosing strong individuals from the population to generate a new population. In this study, random competition and elitist preserved strategy are used; the best individual in the present population is preserved in the next population, and a gamble mechanism is used to choose individuals from the present population.

Hash function searching strategy

By using the hash function, the fitness data calculated in the process of optimization can be saved and applied. The key to the hash table is the superposition of the American Standard Code for Information Interchange (ASCII) code of every number. The methods adopted for constructing the hash function include the fold method and the division method: when the key is folded as the max-length of the no-symbol 64 integer, the position of the key in the hash table is found using the division method. In conflict resolution, all conflict data are recorded in a chain list, including the key and its value. When a key value is added into the sorted hash table, and if there are clashes, it is necessary to record the key value into the chain list, that is, behind the position of the clash. By searching using the key value, a clash is found at the position calculated by the hash function. When the search is continued on the chain list at this position and the relevant value is found, the value is returned; otherwise, a failure is returned.

Empirical verification using real data

To verify the proposed algorithm, real-world data obtained for a typical working week from an RMC distributing firm are applied to perform the test. The real-world data and constraints are modeled by the aforementioned Mixed Integer Programming Model (MIP) model. The test data contain 5-day customer demand data: instances 1–5 (Figure 4). Each customer demand data entry contains information such as customer ID, demand for RMC, and the distance between depot and construction site. There are 20 vehicles in the depot and the loading capacity of each vehicle is $6^{m^{3}}$ . The dynamic demand data for all instances are shown in Figure 5. There are three types of dynamic demand: Newly implies dynamic demand from a new customer; Add implies an increase in RMC needed, while Sub implies a decrease. $T_{r}$ is the time of receipt of dynamic demand, and $[a (c), b' (c)]$ is the start time window. If dynamic demand is Add or Sub, the original scheduling plan should be used for calculating the start time window.

Figure 4.

Customers’ demand data for the baseline plan.

Figure 5.

Customers’ dynamic demand data.

Results

The algorithm is validated using the five instances mentioned above. The results are shown in Table 1. The number of rescheduling times is abbreviated as RT, the time to execute the rescheduling operation is $T_{t}$ , the number of unfinished deliveries is CJ, the number of used vehicles is UV, the total delivery time for all vehicles is TDT, and the total time in waiting at the construction site is TWT. The total objective value is OBJ, and the total execution time of the algorithm is EXT.

Table 1.

Validation checks for dynamic data.

Instance	RT	T_t	CJ	UV	TDT (min)	TWT (min)	OBJ	EXT (s)
1	2	T_t ₁ = 8:48 T_t₂ = 10:55	2	20	3330	86	19,588	628.3424
2	3	T_t ₁ = 8:53 T_t₂ = 9:41 T_t₃ = 11:41	0	20	2346	32.5	12445.5	624.3804
3	1	T_t ₁ = 9:26	0	11	2346	23.5	7916	473.3290
4	3	T_t ₁ = 8:20 T_t₂ = 9:18 T_t₃ = 11:09	0	16	2331	29.5	10420.5	789.2348
5	2	T_t ₁ = 8:12 T_t₂ = 9:48	0	20	2844	66	13,042	633.8352

Rescheduling occurs twice. In the first rescheduling, two new customers’ demands (i.e. customers 5 and 6) are added. All former customers’ dynamic demands are handled in the subsequent rescheduling. Vehicle flow for instance 1 is given and the results of the algorithm are in the list structure. For example, in Figure 6, vehicle 1 reaches depot node $D_{10}$ from beginning node S. After loading from the depot, it delivers concrete to the construction site for the first job of customer 2 ( $C_{2} J_{1} (7 : 00)$ ; 7:00 is the start unloading time at the construction site), and then, it returns to the depot and begins to do the next loading for the second job of customer 3 ( $C_{3} J_{2} (7 : 49)$ ) at the relevant time of depot node $D_{24}$ until the whole operation is fulfilled. The vehicle returns and is parked at the depot (P). The twice-rescheduling results are shown in Figures 7 and 8.

Figure 6.

Vehicle flow under baseline plan for instance 1.

Figure 7.

Vehicle flow at first rescheduling for instance 1.

Figure 8.

Vehicle flow at second rescheduling for instance 1.

It can be seen in Figure 7 that at the time of executing the first rescheduling (8:48), four deliveries of customer 1 and all deliveries of customer 2 are finished, and six deliveries of customer 3 and three deliveries of customer 4 are started. The result of the first rescheduling shows that the last two deliveries of the new customer, customer 6, cannot be completed. This is because no depot nodes can be found for these two deliveries. Now, we demonstrate the time for rescheduling in the presence of new demands and analyze the results.

Analysis of the results

To achieve the results, we use a strategy (called “base strategy”) where the time of rescheduling is set to the time of dynamic demands. The result for instance 1 is shown in Table 2, and the results for instances 2–5 are shown in Table 3. It is seen that there are two deliveries of customer 6 that have not been completed yet, and the objective value of this result is consistent with the objective value obtained in the previous section. The result shows that this method is more time-consuming than the strategy we proposed, and the rescheduling operation is executed more times than the aforementioned strategy. If the dynamic needs of customers appear frequently, then the system reschedules frequently, which results in constant adjustment of the vehicles’ order in the depot. Consequently, the planning of vehicle movement cannot be conducted in a timely manner, causing delays in loading/unloading. In the aforementioned strategy, the execution time of rescheduling is postponed to a more reasonable range (or limit), thus enabling each rescheduling operation to deal with more dynamic demands, minimizing the impact on the original plan and rescheduling times, eventually minimizing the cost of vehicle order adjustments at the depot and the execution time of the algorithm. In addition, the results in Table 3 show that the operation times of rescheduling and the execution time of the algorithm are both greater than in our strategy.

Table 2.

Instance 1 by base strategy.

Rescheduling No.	T_t	CJ	UV	TDT (min)	TWT (min)	EXT (s)
1	T_t ₀ = 0:00	0	13	2490	58.5	267.4751
2	T_t ₁ = 8:00	0	19	3249	76.5	336.2413
3	T_t ₂ = 8:30	2	20	3375	88	323.5133
4	T_t ₃ = 10:30	2	20	3282	86.5	64.8231
5	T_t ₄= 10:40	2	20	3330	85.5	58.9621

No. of reschedulings: 5; objective value: 19585.5; total execution time of algorithm: 1051.0149 s.

Table 3.

Instances 2–5 by base strategy.

Instance ID	RT	UV	TDT (min)	TWT (min)	OBJ	EXT (s)
2	6	20	2346	20.5	12407.5	1436.4362
3	3	11	2346	16.5	7895	591.3019
4	6	16	2331	27	10413	1049.5813
5	5	20	2844	59.5	13022.5	1537.9107

Hash function search strategy of optimization

The hybrid GA is used to calculate the objective value. First, jobs are inserted into RMCV flows. Then, given vehicle flows, the objective value is calculated. This calculation process is relatively time-consuming, and thus, a hash function search strategy is used to save and use historical data to improve algorithm efficiency. Figure 9 shows the number of collisions when the search is made from the hash table for generation of the executing sequence of instance 1.

Figure 9.

Number of collisions among individuals.

As seen in Figure 9, when all individuals are saved in a hash table, the population size of each generation is 30 individuals. The hash function search is an instant one: time spent is negligible as compared to the time spent in the calculation of the objective value. Without the hash function searching strategy, executing 2000 generations of instance 1 (shown in Figure 9, the total number of collisions here is 40,121) requires 1027.320130 s, while using the same takes only 289.301319 s. This is only 28.16% of the earlier computation time and saves about 13 min when the hash function search is used. It is found that the hash search strategy can effectively improve algorithm efficiency and mitigate the complexity in calculating the objective value.

Conclusion

RMCV scheduling faces a dynamically varying environment and various uncertainties. This study established an RMCV rescheduling system that can accommodate dynamically varying customer demands caused by uncertainties at construction sites. The proposed method executed rescheduling as per the dynamic level of demand and employed a heuristic hybrid GA to optimize the rescheduling of RMCVs given system state at that time. The proposed method’s effectiveness was confirmed via an application to real data. This study focused on uncertainties at the end-use point (i.e. at a construction site) as the causes of the variation in demand, while neglecting uncertainties in the transportation process. This is left for future research.

Footnotes

Appendix 1 Declaration of conflicting interests

The author(s) declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article.

Funding

The author(s) received no financial support for the research, authorship, and/or publication of this article.

References

Durbin

Hoffman

OR practice—the dance of the thirty-ton trucks: dispatching and scheduling in a dynamic environment. Oper Res 2008; 56: 3−19.

Bertsimas

DJ.

A vehicle routing problem with stochastic demand. Oper Res 1992; 40: 574–585.

Gendreau

Laporte

Seguin

A tabu search heuristic for the vehicle routing problem with stochastic demands and customers. Oper Res 1996; 44: 469–477.

Lei

Laporte

Guo

The capacitated vehicle routing problem with stochastic demands and time windows. Comput Oper Res 2011; 38: 1775–1783.

Tan

Cheong

Goh

CK.

Solving multi objective vehicle routing problem with stochastic demand via evolutionary computation. Eur J Oper Res 2007; 177: 813–839.

Lin

Chou

SY.

Solving the truck and trailer routing problem based on a simulated annealing heuristic. Comput Oper Res 2009; 36: 1683–1692.

Derigs

Pullmann

Vogel

Truck and trailer routing—problems, heuristics and computational experience. Comput Oper Res 2013; 40: 536–546.

Mirmohammadsadeghi

Shamsuddin

Memetic heuristic approach for solving truck and trailer routing problems with stochastic demands and time windows. Netw Spat Econ 2015; 15: 1093–1115.

Mirmohammadsadeghi

Shamsuddin

Metaheuristic approaches for solving truck and trailer routing problems with stochastic demands: a case study in dairy industry. Math Probl Eng 2015; 2015: 494019.

10.

Tommelein

AEY

. Just-in-time concrete delivery: mapping alternatives for vertical supply chain integration. Proc IGLC 1999; 7: 97–108.

11.

Matsatsinis

NF.

Towards a decision support system for the ready concrete distribution system: a case of a Greek company. Eur J Oper Res 2004; 152: 487–499.

12.

Feng

Cheng

HT.

Optimizing the schedule of dispatching RMC trucks through genetic algorithms. Automat Constr 2004; 13: 327–340.

13.

Feng

HT.

Integrating fmGA and CYCLONE to optimize the schedule of dispatching RMC trucks. Automat Constr 2006; 15: 186–199.

14.

Naso

Surico

Turchiano

et al . Genetic algorithms for supply-chain scheduling: a case study in the distribution of ready-mixed concrete. Eur J Oper Res 2007; 177: 2069–2099.

15.

Yan

Lai

An optimal scheduling model for ready mixed concrete supply with overtime considerations. Automat Constr 2004; 16: 734–744.

16.

Yan

Lai

Chen

Production scheduling and truck dispatching of ready mixed concrete. Transport Res E: Log 2008; 44: 164–179.

17.

Yan

Lin

Liu

YC.

Optimal schedule adjustments for supplying ready mixed concrete following incidents. Automat Constr 2011; 20: 1041–1050.

18.

Yan

Lin

HC.

A planning model with a solution algorithm for ready mixed concrete production and truck dispatching under stochastic travel times. Eng Optimiz 2012; 44: 427–447.

19.

Asbach

Dorndorf

Pesch

Analysis, modeling and solution of the concrete delivery problem. Eur J Oper Res 2009; 193: 820–835.

20.

Schmid

Doerner

Hartl

et al . A hybrid solution approach for ready-mixed concrete delivery. Transport Sci 2009; 43: 70–85.

21.

Schmid

Doerner

Hartl

et al . Hybridization of very large neighborhood search for ready-mixed concrete delivery problems. Comput Oper Res 2010; 37: 559–574.

22.

Heywood

Chan

Chatwin

CR.

Application of stochastic real-valued reinforcement neural networks to batch production rescheduling. Proc IMechE, Part B: J Engineering Manufacture 1997; 211: 591–603.

23.

Mirchandani

Borenstein

The vehicle rescheduling problem: model and algorithms. Networks 2007; 50: 211–229.

24.

Wang

Zhang

Fuh

JYH

. Job rescheduling by exploring the solution space of process planning for machine breakdown/arrival problems. Proc IMechE, Part B: J Engineering Manufacture 2011; 225: 282–296.