Printer Friendly

A more realistic approach towards concrete delivery dispatching problem: using real distance instead spatial distance.

1. Introduction

It is proven that the Ready Mixed Concrete Dispatching Problem (RMCDP) is NP-hard in the strong sense (Asbach, Dorndorf, and Pesch 2009), thus, finding an optimum solution using mathematical models can be computationally expensive and, even in reasonably sized instances, practically impossible, using today's computing facilities. For this reasons, experts are trusted to handle the decision-making in concrete dispatching (Maghrebi and Travis Waller 2014). The reliance on human reasoning to solve a problem, that although complex, has very important applications, makes it imperative to improve the computational methods that are used to tackle this issue. Beyond the computationally expensive time, the use of spatial distance rather than real distance can be considered as another challenge of the optimisation approach. The Ready Mixed Concrete Problem (RMCP) has large applicability, given that the complexity of the problem challenges experts in concrete batching plants on a daily basis. Therefore, several optimisation models that aim to guarantee optimal decision-making in concrete dispatching have been proposed. Most of these methods target, directly or indirectly, to minimise the operational cost of the delivery process, which is intrinsically related to the travel time of the trucks. This key input is commonly calculated using the spatial Euclidian distance - straight line between the origin and destination points - and some records of experimental data for the mean velocity for trucks. However, as the path actually travelled by the trucks can differ greatly from a straight line, the accuracy of this calculation method is questionable.

This paper attempts to analyse the implications of the inaccuracy of the spatial method for travel time calculation. For this end, a new method of obtaining the travel time is proposed, using real data acquired using Google Maps API. The delivery decisions made using this approach are then compared to those obtained with the spatial calculation. The conclusions drawn from this comparison bring to light the importance of calculating travel time in a more realistic way and, thus, foment further interest in acquiring more information about this input. In practice, RMC companies will be able to make more accurate decisions that will lead to decreases in operational costs and environmental impacts. Figure 1 shows a representation of both the spatial and the real distance between a concrete batching plant and one customer, in Adelaide, Australia. The difference in length between both paths is significant. This suggests that adopting a more accurate way to determine distance and travel time leads to a better quality in the delivery choices. Using Google Maps API as a rich source of information in decision support systems has recently received a growing body of attention in other fields such as (Kim et al. 2012; Yu et al. 2013).

The proposed method was tested with a field data base gathered from an active RMC in the region of Adelaide, Australia. The paper is organised as follows: Section 2 summarises the existing literature on the RMC delivery problems; Section 3 presents the mathematical formulation of RMCDP; Section 4 details the method adopted to obtain and apply the real travel time. Section 5 gives further insight on the system which we aim to optimise; Section 6 describes and discusses the results obtained and is followed by the conclusion section.

2. Related works

In the literature, it is possible to identify numerous approaches for finding an optimum or near optimum solution to the RMCDP. Hoffman and Durbin (2008) present a practical and theoretical analysis of the RMCDP by using time-space networks that handle multiple alternatives of fixed-time deliveries and aims to maximise revenue. Nonetheless, the use of homogeneous trucks makes their analysis less realistic. Tommelein and Li (1999), also perform an overview of the ready mixed concrete production and delivery systems, regarding it as an example of a Just- in- Time process. They analyse two different forms of vertical supply chain integration for the delivery of concrete, which differ in who owns and controls the delivery trucks schedules, the contractor or the batching plant. They conclude that the preferable alternative depends on the context of the delivery. Heuristic approaches have been widely used to find reasonable results for the RMCDP in small intervals of time. Feng, Cheng, and Wu (2004) provide a good overview of the RMCDP and propose the use of a Genetic Algorithm (GA) to improve the efficiency of the deliveries as well as to minimise the truck idle time. However, as they consider only a single depot, a homogenous fleet and very small instances, their model distances from reality. Naso et al. (2007) also use GA but in a much more sophisticated way. By adopting a multi-objective approach, and considering more elements of the concrete dispatching practicalities, they achieve a more accurate solution. Lu and Lam (2005) create a powerful tool for concrete dispatch scheduling, by combining discrete event simulation and genetic algorithms (GA). They apply this tool, which is called HKCONSIM to optimise the operations of a RMC in Hong Kong. Their model shows especially good results when fine-tuning input models are employed. The paper compares a more robust version of Genetic Algorithm (Robust-GA) and Column Generation (CG) using examples of real RMC problems. The results show that, although the computational cost of the CG solution is lower, Robust-GA converges faster. The effectiveness of Robust-GA is also tested on (Maghrebi, Waller, and Sammut 2013). The use of the genetic algorithm approach is also presented by Garcia, Lozano and Canca (2004) however, as they adopt a multi-depot context, the complexity of the problem is increased. At first they tackle the problem with a Graph-based solution method and, in sequence, attempt to solve the same problem using GA. They reach the conclusion that the solution provided by the GA was achieved with much less computational time and with relatively small deviation from the exact solution. (Cordeau and G.d.e.e.d.r.e.a.d. decisions 2000) presents a multi-commodity network flow formulation with time and capacity constraints for the VRPTW, considering one depot only. Cordeau analyses approximation methods proposed in the literature to derive upper bounds for the model and optimisation tools used to determine lower bounds. Additionally, he analyses optimal approaches to produce integer solutions. As a conclusion, Cordeau states that both approximate and optimisation methods were successful and identifies the use of hybrid methods as an important direction for future research. A good example of the use of a hybrid approach is at (Schmid et al. 2009, 2010). In (Schmid et al. 2009), Schmid discusses a novel approach for creating schedules for concrete dispatching, by integrating integer multi-commodity network flow (MCNF) IP techniques and variable neighbourhood search (VNS) techniques. Additionally, he considers vehicles that require specialised unloading equipment, increasing the complexity of the problem. The scheduling of unloading equipment is also considered in Matsatsinis (2004) and Zhang, Li, and Liu (2011). Other heuristic methods have been employed to tackle the RMCDP, such as Ant Colony, (Silva et al. 2005) Particle Swarm Optimisation (PSO) (Liu et al. 2010), Bee Colony Optimisation (BCO) (Srichandum and Rujirayanyong 2010), Tabu Search (TS) (Srichandum and Rujirayanyong 2010), sequential-GA (Maghrebi, Travis Waller, and Sammut 2014), Column Generation (Maghrebi et al. 2016).

Alternatively, there are methods that aim to achieve an exact optimal solution, however, given that the RMCDP is proven to be NP-hard, these are limited to smaller instances. Asbach, Dorndorf, and Pesch (2009) propose a new formulation for the problem, by dividing the customers and depots into sub-customers and sub-depots to handle multiple deliveries. Nonetheless, this involves a large number of decision variables, which make the model impossible to solve in large instances. To overcome this issue (Asbach, Dorndorf, and Pesch 2009) adopt a combination of local search with the MIP programming. Yan and Lai (2007) and Yan, Lai, and Chen (2008) employ a network flow model that integrates RMC production scheduling and truck dispatching in the same framework, including overtime considerations. They formulate the problem as a mixed integer model with side constraints. They also propose a solutio n a Igorithm that, when combined with CPLEX is very helpful for solving large-scale problems. However, their model is sensitive to large schedule perturbations and considers only a single depot. Yan, Lin, and Jiang (2012) use a mathematical solver, together with relaxation techniques to find solutions to the problem. Lin et al. (2010) formulate RMCDP as a job shop problem with recirculation, including time windows, demand post-ponement and external cost of transport in a multi-objective programming model. Although this approach is limited to small and medium instances, it is very interesting as it focuses, not only on minimising costs, but also in achieving a balanced dispatching system that aims to maintain a desirable balance between business operations and environmental protection. Narayanan et al. (2015) applied lagrangian relaxation to solve RMCDP more efficiently.

Maghrebi et al. (2014), employs a Bender decomposition method, aiming to solve larger scaled instances of the RMCDP problem. The conclusion reached is that this approach provides optimum or near optimum solutions in a practical interval of time. In reality however, due to the lack of practical solutions for the Ready-mixed concrete dispatching problem, experts make the delivery choices. The quality of the experts decisions is assessed in (Maghrebi, Sammut, and Waller 2013; Maghrebi, Travis Waller, and Sammut 2015). Maghrebi and Travis Waller (2014) compare the quality of the decisions between integer and mixed integer programming, Genetic algorithms and Experts choices. They show the disparity of the total cost of transportation optimised using each of the four approaches considering increasingly larger instances. They observed that, although MIP always achieved lower costs, when instances reached a certain size it was impossible to obtain results in a polynomial time. Most recently, Maghrebi et al. (2014), proposed a novel approach to a single-de pot ready mixed concrete problem. Their objective was to overcome the conflicting time window issue, by assigning vehicles to independent time slots. They adopted the Mixed Integer programming approach and achieved quick and accurate results, which is promising in spite of the small size of the instances that were analysed. They state that the travel time was calculated using the Euclidean distance and a mean velocity of 30 km/h for trucks. Yan, Lin, and Jiang (2012), calculate this input based on records, however, a buffer incremented to account for the time spent in traffic, is included. Lin et al. (2010) work out the travel time employing a formula that takes under consideration the urban service travel norms.

There are also a few more works that hired machine learning techniques to solve RMCDP. The feasibility of using machine learning techniques in RMCDP was studied by (Maghrebi, Sammut, and Waller 2015). Maghrebi et al. (2016) used machine learning techniques to match experts' decision in RMC dispatching centres. There are similar works that have tried to predict duration of RMC supply process using a novel fusion learning approach (Maghrebi et al. 2016) and hazard methods (Ghasri et al. 2016).

In other similar works, there is no mention of an accurate source for the distance and travel time. In this paper, we propose a new method for obtaining travel time, which consists in importing realistic information from Google Maps. The objective is to improve the accuracy of solutions by employing a better quality input.

3. Methodology

In order to solve the RMCDP, we employ a constrained optimisation model, which consists, basically, in an objective function and constraints. The model describes mathematically a despatching system that contains two basic elements (Figure 2):

Nodes: Refer to Starting Points ([u.sub.s]), Depots (u), Customers (v) and Finish Points ([v.sub.f]);

Vectors: Denote the path travelled by trucks to perform the deliveries.

The system operates as follows: A truck starts at its home depot, which is its start point. It can load on this plant or travel to load at a Depot (v). In sequence and after being loaded with fresh concrete, it heads to a customer to unload. At this point, the truck can go back to a depot, which is not necessarily the same as it came from, to reload and serve other customers. After supplying the assigned customer, the truck's job is terminated after it is backed to a plant that represents its finish point. There is also a possibility where the truck goes directly from the start to the finish point, in this scenario the truck does not perform any deliveries and only is relocated in case of fleet management. An example of this system with a reduced amount of trucks, depots and customers is illustrated in Figure 2.

A delivery starts at a node u and ends in a node v, using truckk. The cost of each delivery is represented by the function z, which based on the travel time between origin and destination. The objective of the optimisation is to minimise function z, given the constraints that will be presented in the next paragraphs. The decision variables of the optimisation are [x.sub.u,v,k], and [??] both of them assume binary values and are defined as follows: [x.sub.u,v,k], = 1 if the route between u and v, using truck k is selected and 0 otherwise; [??] if customer [c.sub.i] is satisfied and 0 otherwise. When the MIP approach is used, one additional decision variable w is considered, which denote the time, within a specific time window, in which the delivery will happen.

The modelling process adopted in this paper is identical as the one introduced by (Asbach, Dorndorf, and Pesch 2009) and was used by other researchers such as (Maghrebi and Travis Waller 2014). The employed notation is described in the notation section and the formulation is presented below:

[mathematical expression not reproducible] (1)

Subject to:

[for all] [member of] K (2)

[for all]k [member of] K (3)

[for all]k [member of] K, v [member of] C [union] D (4)

[for all]v [member of] C(5)

[for all]u [member of] D(6)

[for all]c, v [member of] C(7)

[mathematical expression not reproducible] (8)

[mathematical expression not reproducible] (9)

[U.sub.u] < [w.sub.u] < [L.sub.u] [for all]u [member of] D (10)

The Objective Function (Equation 1), forces the optimisation to find the lowest total transportation cost, supplying the larger possible number of customers. To this end, it considers the summation of the costs of the chosen routes and the cost for not supplying a customer. When a customer [c.sub.i] is left unsupplied, [y.sub.c] becomes 0 and [beta](c), which is a large constant is applied to the sum. This represents a penalty that is considered due to the undesirability of having unsatisfied customers. Equation (2), guarantees that a truck leaves its base only once in the start of the day and, similarly, Equation 3 makes sure that a truck returns only once to the finish depot. Equation (4) certifies that no trucks are consumed or produced in the nodes, i.e. the number of trucks that arrive to a depot/customer is the same as the number of tucks that leave this instance. When u [member of] C, then v [member of] D and j [member of] C, however, if u [member of] D, then v [member of] C and j [member of] [v.sub.f] To deal with the fact that more than one delivery might be made from one certain depot to the same customer in one working day, the depots are divided into a set of sub-depots and the customers into a series of sub-customers. Each sub-depot can serve one sub-customer only with only one truck. For this end, Equations (5) and (6) ensure, respectively that only one truck is sent to a customer and that only a depot supplies a customer. Equation (7) certifies that the demands of the customers are satisfied, and Equation (8) guarantees that the customers are served within the specified time requested. Finally, Equation (9) ensures that the travel time between depot and customer does not extrapolate the permitted delivery time. Given concrete is perishable material and there are limitations regarding the time within it can be transported, this time depends on the type of concrete. In reality in RMC dispatching, there are uncertainties that prevent suppliers from delivering the concrete in exact specific times. Usually some flexibility can be considered and the deliveries can take place a little earlier or later than the requested time. Equation 10 models this issue, and states that deliveries can happen within the time window defined by the boundaries [U.sub.u] and [L.sub.u] , which correspond to flexibility of customer u. Two different approaches for solving the RMCDP have been presented in the beginning of this paper, the Integer Programing (IP), that does not consider time windows, and the Mixed Integer Programing (MIP), that does. In IP, the delivery time is fixed and, thus, its formulation includes all the equations described above, with the exception of Equation (10). Nonetheless, in MIP the delivery time can vary within the time window, and therefore, it becomes another variable that has to be defined by the optimisation. In the former, Equation (10) is considered. In this paper both IP and MIP methods are used to analyse the disparity between the spatial and the realistic approach for travel time calculation. In this sense, it is possible to compare how the difference in accuracy affects both methods. The calculation of the spatial travel time is identical to the one employed in (Maghrebi, Travis Waller, and Sammut 2015), in this sense, it is based on the Euclidean distance and a mean velocity of 30 km/h for trucks. Moreover, the 30 km/hr is summary of generalised non-parametric regression model on actual truck travel times for a wide range of distances obtained from a concrete delivery company.

4. More realistic travel time

The process employed to solve the RMCDP, using realistic data, consisted of five basic steps and involved the use of four different tools. The data exchange and processing steps are illustrated in Figure 3 and briefly described below.

The data, that consist of the geographical coordinates of the depots, costumers, start and finish points, is organised on MATLAB and put in a format that is compatible with the Google Maps API tool. In sequence, the routing information for each origin/destination pair is requested by Google Maps API, which returns the response as a JSON file. The response from Google Maps is then analysed, using MATLAB, and the Travel Time information is extracted and saved on a matrix, in MATLAB. The matrixes that are generated, in turn, are used as an input for the optimisation model that is written in GAMS. Finally, the optimisation model is run with the aid of a powerful server and the results are registered. The purpose of this process is to guarantee that the optimisation model takes into account the real travel time between locations when it makes the delivery decisions. Prior to describing all the steps of the process in details, an explanation about the Google Maps API tool is given in the following paragraph.

Google Maps API is a tool with the purpose of allowing developers to access Google Maps features and customise it, based on their demands. One of the offerings of this service is the Directions API, which, upon request, returns to the user the directions between two locations. It is possible to obtain directions for four different types of transportation: Transit (public transportation services), driving, walking and cycling, as well as specify waypoints and time of departure. The user can request the information using a URL query. Google Maps API returns a JSON file containing a variety of travel related information along with geocode information. The obtained travel time from the origin/destination pair is the most important piece of information needed. The travel time provided by Google maps API represents the time necessary to get from the origin to the destination, taking into account the characteristics of the chosen route and disregarding traffic situation. It is possible to take into account traffic conditions in the response; however, this feature is not available to the public for free. In addition, there is no reference of Google Maps proving to the general public routing information specifically for trucks. In this paper, the travel time for the mode 'driving' is requested and the necessary adaptations that were made to the data in order to make it suitable for trucks are described in this section.

The initial stage of the project consisted of obtaining the Travel Time between the nodes in the dispatching system. The analysed system was based on real database from a Concrete Dispatching company in Adelaide, Australia. Therefore, we used the geographic coordinates of real depots and customers, aiming to optimise the deliveries, which rely on the history of a former working day. A static approach is used, thus, all the data are available before the optimisation is initiated.

Firstly, we prepared the data, which was composed by the latitudes and longitudes of Depots and Customers, setting it into a specific format accepted as input for the Google Maps API. Then, the travel time from each origin to its destination was retrieved using MATLAB to explore the obtained JSON files.

MATLAB was used to extract the travel time information from the Google Map's response and generate a matrix with the travel times from each origin destination pair. During the dispatching process, there are four types of travel that can be performed by the trucks:

* Start [right arrow] Depot

* Depot [right arrow] Customer

* Customer [right arrow] Depot

* Customer [right arrow] Finish

They can go from their start point to a depot to load, from a depot to a customer to unload, from a customer to a depot to reload and, finally, from a customer to the finish point. In this sense there are four different Travel Time matrixes that have to be considered: The Travel From Depot, which contemplates the depots as origins and customers as destinations; the Travel To Finish, which considers the customers as origins and the Finish Point as destinations; the Travel From Start, that considers start point as origins and depots as destinations and the Travel Return, that regards customers as origins and depots as destinations.

When the travel times are retrieved from Google Maps, the mode 'driving' was considered, this means that the response was based on the performance of cars. It is known that there is significant difference between the durations of travels for concrete dispatching trucks and regular cars, due to the characteristics of the vehicle and special considerations at roads. To overcome this issue we tried to find a meaningful correlation between trucks travel time and regular cars travel times. We observed 129 trucks trips and compared the real travel times with travel times obtained from Google Maps API. The second order polynomial relationship that is shown in the below was found to be the most accurate formulation to obtain trucks travel times from the car travel times retrieved from Google Maps API.

0.000131 x [(Travel Time for cars).sup.2]

+ 0.8346 x (Travel Time for cars) + 325.2

This formulation was applied to all the travel time matrixes retrieved from Google Maps, guaranteeing, thus, a closer correspondence to reality.

Then, General Algebraic Modelling System (GAMS), a high-level modelling system for mathematical programming and optimisation, was used to model the optimisation problem with the formulations described in Section 3. Altogether, there were four optimisation models, given the two different ways to calculate travel time (spatial and real) were contemplated, in turn, in each of the two approaches, with and without flexible time windows. The complexity of the optimisation, together with the size of the instance analysed made it practically impossible to perform the optimisation in a personal computer. Therefore, the optimisation was performed on a shared server (8 Intel Xeron CPU @3.6GHZ, 188 GB RAMS, CentOS Linux release 7.0.1406) which was powerful enough to provide solutions in a reasonable interval of time.

5. Case study

In this paper, we assess the inaccuracy of the spatial method for calculating travel time, by proposing a more realistic way to obtain this input, with Google Maps, and comparing the results of applying both approaches in IP and MIP optimisation models. The proposed approach is tested using data obtained from a day of an active RMC in Adelaide, Australia. On this specific day, they supplied fresh concrete to 58 different customers in 130 deliveries. The dispatching was made from 4 different depots, using 34 trucks and considering 9 start and finish points.

In the analysed working day, the demand for the first delivery was at 4:20 am and the last at 6:25 pm Therefore, in order to shorten the number of variables in the problem we considered a working day starting at 2:30 am and ending at 6:30 pm The depots were divided into a series of sub-depots according to the time of service, which had an interval of ten minutes from one sub-depot to the next. In this sense, 388 sub-depots were considered. Additionally since, some customers demanded a volume of concrete larger than the capacity of truck; they were divided in sub-customers resulting, thus, in a series of 130 customers.

6. Results and discussion

In this section, we compared the optimal decisions for the RMCDP using the real and the spatial travel time. The solutions were obtained using two different optimisation models: IP and MIP. The overall cost, which corresponds the total travel time, in minutes, for the four different approaches is described on Table 1.

The immediate conclusion is that there is no difference in total costs between the IP and MIP approaches. This outcome is reasonable, given the fact that both models tend to reach similar or identical results for small instances. Therefore, this means that, in this case, relaxing the time of the delivery within a time window has no effect in the overall cost. Secondly, we analyse the differences between the costs of the two travel time calculation approaches. As detailed on Table 1, the total cost for the real travel time method (RTT) was approximately 21.3% higher than the spatial travel time approach (STT). This was expected, given the real distance between two locations is greater than the straight line that connects them. We may conclude that the cost related to the proposed method is significantly different and of course more accurate.

In order to reveal the practical difference between two approaches rather than cost, the difference in the choices regarding which depot should serve which customer was investigated in detail. Altogether, when the IP approach was adopted there were 120 different decisions, which represent 92.3% of the deliveries. Because both, depots and customers, were divided into a series of sub-depots and sub-customers, a different delivery choice did not necessarily mean that the customer was served by a different depot, it could mean that it was served only within a different time slot. Therefore, whether or not customers are being attended by an alternative depot is a different question. Now, addressing this inquiry, we conclude that a much smaller number of deliveries originated from a different depot, when we compare the proposed method with the spatial one. Considering the IP method, 10 deliveries were made from different depots when the real travel time approach was adopted, representing 7.7%.

In the following, the main differences between the two approaches are illustrated. The Figures 4-8 illustrate the optimal delivery relationships between customers and depot, established by each of the four optimisation models. In these figures, the blue dots represent the customers and are plotted based on their geographic coordinates. Every line represents a delivery and it is plotted from the depot location to the costumers, the number of identical delivery relationships is represented by the line's width.

In Figure 4, there are four diagrams representing the decisions for each model. In Figures 5 and 6 the different choices made in each method are highlighted. Figure 7 shows the delivery relationships from the two methods overlayed, in order to make explicit the manner in which the decisions changed.

In Figure 4, it may be clearly observed that, whereas there are no differences between the delivery choices made using the IP and the MIP approaches, it is possible to note significant disparity in the results regarding the real and spatial travel time. In order to better analyse the impact of changing the quality of the travel time input the results, Figures 5-7 are provided.

In Figure 5, we identify, in the Spatial Travel Time solution diagram, the delivery relationships that cease to exist when we alternate from this approach to the Real Travel Time one. Figure 6, in turn, shows the alternative decisions, highlighted in red, on the Real Travel Time solution diagram. Finally, Figure 7 illustrates both the solution diagrams overlayed; the Spatial Travel Time choices are represented in grey and the Real Travel Time decisions in blue. Similarly to Figure 5, red lines represent the relationships that change from the Spatial to the Real Travel Time model. In this sense, the delivery relationships that are common to both approaches are shown in grey, the ones that only exist the spatial model, in red and the choices that are exclusive to the Real Travel Time model are represented in blue. Therefore, these pictures fully illustrate how the delivery relationship network changes when we apply a more realistic travel time input.

Figure 8 illustrates both the real and the spatial distance between the depots and the customers they have been assigned to. It is clearly shown that the real path that would be travelled by the trucks differs greatly from a straight line, thus it is possible to understand why the delivery decisions are different in the two models. This is consistent with the discrepancy we observed in the results from the optimisation model, and reinforces the notion that a better quality travel time input leads to significantly distinct and more accurate results.

7. Conclusion

In this paper, a novel method of obtaining the travel time for Concrete Dispatching is proposed. The objective is to improve the accuracy of this input, by retrieving real travel time information from the Google Maps API. The travel time information is requested with the use of an URL, and the response, given in a JSON format, is analysed on MATLAB. The matrix of travel times that is obtained is used as an input in the optimisation models. The quality of this approach is tested by comparing the outcome of two optimisation models, IP and MIP, employing, in turn, the real travel time and a spatial travel time, which is based in the Euclidian distance between two points.

In the results section, it is shown that the overall cost for the optimisation regarding the travel time from Google Maps is 21.3% greater than the one obtained from the spatial travel time. This difference reflects the fact that the real travel time is significantly greater than the spatial one, and brings to light the impact that this input has on the optimal solution. When the delivery decisions from the two models were compared, it was possible to conclude that, from the 130 delivery decisions, 120 were different, which means that 92.3% of the dispatches were made by a different depot or within an alternative time slot. In addition, 10 from the 120 different decisions involved the selection of an alternative depot to perform the delivery, what represents 7.7% of the total number of dispatches. Therefore, it is possible to assume that, for the analysed instance, a change in the way travel time was calculated had great impact in the solution of the optimisation, regarding, not only the overall cost, but also the delivery decisions. These results reveal the importance of obtaining accurate information for the travel time between locations when assessing the RMCDR Since this paper has shown promising results, it is relevant to establish challenges for future works. In order to further analyse how the travel time input affects dispatching decisions, the intention is to employ the proposed travel time calculation method in more instances and observe how the results from the comparisons change, as the number of deliveries increase. Additionally, it is pertinent to further improve the accuracy of the travel time, by obtaining routing information specific for trucks and by taking into account the real time traffic situation in the duration of the travels.

Symbol          Description
C               set of customers
D               set of depots
K               set of vehicle
Us              set of starting points
Vf              set of ending points
[s.sub.u]       service time at the depot u
[t.sub.u,v,k]   travel time between u and v with vehicle k
[q.sub.k]       maximum capacity of vehicle k
[q.sub.c]       demand of customer c
Wo              time at location o
[[beta].sub.c]  penalty of unsatisfying the customer c
M               a big constant
[??]            maximum time that concrete can be hauled
xuvk            1 if route between u and v with vehicle k is used,
                0 otherwise.
yc              1 if total demand of customer c is supplied, 0
Z(u,v,k)        cost of travel between u and v with vehicle k

Disclosure statement

No potential conflict of interest was reported by the authors.

Notes on contributors

Julia Muniz de Miranda Sa is a final year student at the School of Civil Engineering, University of Minas Gerais, Brazil. During 2014-2015, she visited School of Civil and Environmental Engineering, University of New South Wales. Her main research interests include the optimally solving logistics problems and water resources management.

Mojtaba Maghrebi is an assistant professor at Department of Civil Engineering, Ferdowsi University of Mashhad, Iran. Meantime, he is an adjunct lecturer at School of Civil and Environmental Engineering, University of New South Wales (UNSW), Australia. His main research interests are construction management, operation research and data mining.


Asbach, L., U. Dorndorf, and E. Pesch. 2009. 'Analysis, Modeling and Solution of the Concrete Delivery Problem." European Journal of Operational Research 193 (3): 820-835.

Cordeau, J.-E., and G.d.e.e.d.r.e.a.d. decisions, The VRP with Time Windows. 2000. Montreal: Groupe d'etudes et de recherche en analyse des decisions.

Feng, C.-W., T.-M. Cheng, and H.-T. Wu. 2004. "Optimizing the Schedule of Dispatching RMC Trucks through Genetic Algorithms." Automationin Coustruction 13 (3): 327-340.

Garcia, J., S. Lozano, and D. Canca. 2004. "Coordinated Scheduling of Production and Delivery from Multiple Plants." Robotics and Computer-Integrated Manufacturing 20 (3): 191-198.

Ghasri, M., M. Maghrebi, T. H. Rashidi, and S. T. Waller. 2016. "Hazard-based Model for Concrete Pouring Duration using Construction Site and Supply Chain Parameters." Automation in Construction 71: 283-293.

Hoffman, K., and M. Durbin. 2008. "The Dance of the Thirty Ton Trucks." Operations Research 56 (1): 3-19.

Kim, H. J., S. Lim, J. Moon, B. Kim, and E. S. Jung. 2012. 'A Photographic Forensic Case Study: Myths, Principles and Techniques." Mathematical and Computer Modelling 55 (1): 3-11.

Lin, P.-C., J. Wang, S. H. Huang, and Y. T. Wang. 2010. "Dispatching Ready Mixed Concrete Trucks Under Demand Postponement and Weight Limit Regulation." Automation in Construction 19 (6): 798-807.

Liu, P., L. Wang, X. Ding, and X. Gao. 2010. "Scheduling of Dispatching Ready Mixed Concrete Trucks Trough Discrete Particle Swarm Optimization." In Systems Man and Cybernetics (SMC), 2010 IEEE International Conference on, 4086-4090. IEEE.

Lu, M., and H.-C. Lam. 2005. "Optimized Concrete Delivery Scheduling using Combined Simulation and Genetic Algorithms." In Proceedings of the 37th Conference on Winter simulation, 2572-2580. Winter Simulation Conference.

Maghrebi, M., S. Travis Waller, and C. Sammut. 2013. "Scheduling Concrete Delivery Problems by a Robust Meta Heuristic Method." In Modelling Symposium (EMS), 2013 European, 375-380. IEEE.

Maghrebi, M., C. Sammut, and T. Waller. 2013. "Reconstruction of an Experts Decision Making Expertise in Concrete Dispatching by Machine Learning "Journal of Civil Engineering and Arch itecture 7 (12): 1540-1547.

Maghrebi, M., S. Travis Waller, and C. Sammut.2014. "Assessing the Accuracy of Expert-Based Decisions in Dispatching Ready Mixed Concrete." Journal of Construction Engineering and Management 140 (6): 06014004. doi:10.1061/(ASCE) CO.1943-7862.0000853.

Maghrebi, M., and S. Travis Waller, and C. Sammut. 2014. "Sequential Meta-heuristic Approach for Solving Large-Scale Ready-Mixed Concrete-dispatching Problems." Journal of Computing in Civil Engineering 30 (1): 04014117.

Maghrebi, M., V. Periaraj, S. T. Waller, and C. Sammut. 2014. "Using Benders Decomposition for Solving Ready Mixed Concrete Dispatching Problems." In 31st International Symposium on Automation and Robotics in Construction and Mining, 1. Sydney, NSW, Australia: Univ. ofTechnology.

Maghrebi, M., D. Rey, S. T. Waller, and C. Sammut. 2014. "Reducing the Number of Decision Variables in Ready Mixed Concrete for Optimally Solving Small Instances in a Practical Time." In CSCE 2014 General Conference, 1. Halifax.

Maghrebi, M., S. T. Travis Waller, and C. Sammut. 2015. "Optimality Gap of Experts' Decisions in Concrete Delivery Dispatching." Journal of Building Engineering 2: 17-23.

Maghrebi, M., C. Sammut, and S. T. Waller. 2015. "Feasibility Study of Automatically Performing the Conerete Delivery Dispatching through Machine Learning Techniques." Engineering, Construction and Architectural Management 22 (5): 573-590.

Maghrebi, M., V. Periaraj, S. T. Waller, and C. Sammut. 2016. "Column Generation-based Approach for Solving Large-scale Ready Mixed Concrete Delivery Dispatching Problems." Computer-Aided Civil and Infrastructure Engineering 31 (2): 145-159.

Maghrebi, M., T. Waller, and C. Sammut. 2016. "Matching Experts' Decisions in Concrete Delivery Dispatching Centers by Ensemble Learning Algorithms: Tactical Level." Automation in Construction 68:146-155.

Maghrebi, M., M. Maghrebi, A. Shamsoddini, A. Shamsoddini, S. T. Waller, and S. T. Waller. 2016. "Fusion Based Learning Approach for Predicting Concrete Pouring Productivity based on Construction and Supply Parameters." Construction Innovation 16 (2): 185-202.

Matsatsinis, N. R 2004. "Towards a Decision Support System for the Ready Concrete Distribution System: A Case of a Greek Company." European Journal of Operational Research 152 (2): 487-499.

Narayanan, P. K., D. Rey, M. Maghrebi, and S. T. Waller. 2015. "Using Lagrangian Relaxation to Solve Ready Mixed Concrete Dispatching Problems." Transportation Research Record: Journal of the Transportation Research Board 2498: 84-90.

Naso, D., M. Surico, B. Turchiano, and U. Kaymak. 2007. "Genetic Algorithms for Supply-chain Scheduling: A Case Study in the Distribution of Ready-mixed Concrete." European Journal of Operational Research 177 (3): 2069-2099.

Schmid, V., K. R Doerner, R. R Hartl, M. W. Savelsbergh, W. Stoecher. 2009. "A Hybrid Solution Approach for Ready-mixed Concrete Delivery." Traasportation Science 43 (1): 70-85.

Schmid, V., K. RDoerner, R. R Hartl, and J. J. Salazar-Gonzalez. 2010. "Hybridization of very Large Neighborhood Search for Ready-mixed Concrete Delivery Problems." Computers & Operations Research 37 (3): 559-574.

Silva, C., J. M. Faria, P. Abrantes, J. M. C. Sousa, M. Surico, and D. Naso. 2005. "Concrete Delivery using a Combination of GA and ACO." In Decision and Control, 2005 and 2005 European Control Conference. CDC-ECC'05. 44th IEEE Conference on, 7633-7638. IEEE.

Srichandum, S., and T. Rujirayanyong. 2010. "Production Scheduling for Dispatching Ready Mixed Concrete Trucks using Bee Colony Optimization." American Journal of Engineering and Applied Sciences 3(1): 823-830.

Tommelein, I. D., and A. Li. 1999. "Just-in-time Concrete Delivery: Mapping Alternatives for Vertical Supply Chain Integration." In Proceedings IGLC, 97.

Yan, S., and W. Lai. 2007. "An Optimal Scheduling Model for Ready Mixed Concrete Supply with Overtime Considerations." Automation in Construction 16 (6): 734-744.

Yan, S., W. Lai, and M. Chen. 2008. "Production Scheduling and Truck Dispatching of Ready Mixed Concrete." Transportation Research Part E: Logistics and Transportation Review 44 (1): 164-179.

Yan, S., H. Lin, and X. Jiang. 2012. "A Planning Model with a Solution Algorithm for Ready Mixed Concrete Production and Truck Dispatching Under Stochastic Travel Times." Engineering Optimization 44 (4): 427-447.

Yu, X., W. Zhang, L. Zhang, V. O. Li, J. Yuan, and I. You. 2013. "Understanding Urban Dynamics based on Pervasive Sensing: An Experimental Study on Traffic Density and Air Pollution." Mathematical and Computer Modelling 58 (5): 1328-1339.

Zhang, Y., M. Li, and Z. Liu. 2011. "Vehicle Scheduling and Dispatching of Ready Mixed Concrete." In Advanced Computational Intelligence (IWACI), 2011 Fourth International Workshop on, 465-472. IEEE.

Julia Muniz de Miranda Sa (a) and Mojtaba Maghrebi (b)

(a) School of Civil and Environmental Engineering, University of New South Wales (UNSW), Sydney, Australia; (b) Department of Civil Engineering Ferdowsi University of Mashhad, Mashhad, Iran

CONTACT Mojtaba Maghrebi,


Received 22 February 2016

Accepted 27 August 2017
Table 1. Total operational cost in minutes for the RMCDP.

                           IP                      MIP
                Real       Spatial      Real       Spatial

Cost (minutes)  5980.4751  4930.240066  5980.4751  4930.240066
COPYRIGHT 2018 The Institution of Engineers, Australia
No portion of this article can be reproduced without the express written permission from the copyright holder.
Copyright 2018 Gale, Cengage Learning. All rights reserved.

Article Details
Printer friendly Cite/link Email Feedback
Author:Sa, Julia Muniz de Miranda; Maghrebi, Mojtaba
Publication:Australian Journal of Civil Engineering
Article Type:Report
Date:Apr 1, 2018
Next Article:Haul road rolling resistance and pavement condition.

Terms of use | Privacy policy | Copyright © 2021 Farlex, Inc. | Feedback | For webmasters