Dynamic milk-run OEM operations in over-congested traffic conditions

Highlights

• Traditional OEM routes to collect components very often show unperformed tasks.

• Large cities show occasional over-congested traffic conditions.

• A dynamic alternative is to use auxiliary vehicles to perform exceeding tasks.

• We use probabilistic sequential analysis to foresee urban traffic surges.

• The dynamic approach substantially reduces unperformed collecting tasks.

Abstract

Dynamic vehicle routing problems have received increasing attention in the literature due to the rapid IT evolution as well as advances in computing and modelling techniques. In areas subject to critical and often unpredictable traffic congestions, logistics operators often allocate excessive number of collecting tasks to their vehicles, generating unperformed activities due to OEM JIT time constraints and thus violating contractual obligations assumed with their clients. In this paper, a dynamic OEM picking-up (milk-run) routing problem is analysed, in which tasks that likely will exceed the time limit in a route are assigned to supplementary vehicles, thus forming auxiliary dynamic routes formed with the transferred tasks originated from the regular trucks. To solve the problem, a genetic algorithm model was developed in association with a simulation program intended to define some relevant probabilistic parameters. The results have shown that the dynamic formulation considerably improves the service level when compared with the static version.

Introduction

In an OEM operational framework, manufacturing systems are normally organised in a spatially distributed form. An unbalanced and unstable integration of manufacturing and transport systems can impair the competiveness of supply chains. This integration is even more relevant along global supply chains due to longer transport lead-times and the network complexity of manufacturing processes. Furthermore, most large industrial companies have concentrated their efforts on core competence, and consequently tend to transfer logistic operations to service providers. In fact, the process of shipping components from suppliers to OEM industries is quite complex, requiring strict quality assurance control of logistics operations, both at the OEM premises and at its suppliers.

The objective of this study is to investigate a dynamic assignment of vehicles to perform a daily OEM pick-up service on a region subject to occasional unpredictable and severe traffic congestions, caused by serious accidents, public transport strikes, heavy rain, etc. The routing problem to be analysed in this paper comprises a homogeneous fleet of regular vehicles, with each vehicle assigned to a pre-defined district, plus a number of auxiliary vehicles intended to perform part of the collecting tasks whenever the actual traffic condition does not permit the regular fleet to accomplish the service in due time. The logistics operator has been contracted to collect components from suppliers, take them to a central depot, transfer the cargo overnight in long-haul trucks, and deliver the components to OEM clients located in another towns. On-time delivery is an important logistics attribute, meaning that unperformed pick-ups along the routes cause large safety inventory costs and manufacturing delays. The specific objectives of the model are: (a) to guarantee that the unperformed tasks in each vehicle tour are not greater than a pre-established service level; (b) to attain a satisfactory (approximate) balance among districts with regard to the rates of unperformed visits; (c) to seek a vehicle fleet that satisfies (a) and (b) and, at same time, minimises the overall operating costs. In Dynamic Vehicle Routing Problems (DVRP), not all information relevant to the planning of the routes is known by the planner when the routing process begins, and information may change after the initial routes have been constructed. In the application object of this work, although the vehicle service is fully planned in advance, the possible transference of tasks to auxiliary vehicles and the eventual reprogramming of visits lead to changes in the routing process, thus characterising a dynamic behaviour.

In this work, a fault refers to the prospective occurrence of one or more unperformed tasks at the end of the vehicle daily cycle, generated by exceptional delays along the planned route due to occasional severe traffic conditions, and with the consequent penalties (increased inventory costs, fines, manufacturing delays, among others). In general terms, the goal for early fault detection is to have enough time for counteractions such as adding supplementary operations, reconfiguration, maintenance or repair. Earlier fault detection can be achieved by using relationships among the measurable quantities in the form of predicting mathematical models. In this application, the characteristic property selected to reflect the traffic pattern in terms of standard or abnormal conditions, and consequently indicating whether to seek the help of auxiliary trucks or to proceed along the planned route, is the local vehicle speed (the speed within the servicing district). The fault detection process used in this text is the Sequential Probability Ratio Test – SPRT (Basseville and Nikiforov, 1993, Lai, 2001, Wald, 1947).

Traffic information systems, which have been installed in some large cities of the world, aim to increase the flow of vehicles by allowing higher vehicular speeds and by offering less-congested alternative routes to drivers (Fleischmann, Gnutzmann, & Sandvoβ, 2004). The benefits of using such traffic navigational systems in connection with vehicle routing in congested urban areas cannot be denied. But in developing countries, the required large investments to install such systems often forbid its extensive use. One of the objectives of this work is to show that simple dynamic vehicle routing procedures can dramatically improve the logistics performance of the servicing system. With an on-board computer, a fault-detection software, and simple telematics devices linking the vehicle to nearby collaborative agents (other vehicles and the central depot), it is possible to attain better performance levels. By analysing vehicle operational data at specific regeneration points along the route it is possible to anticipate the occurrence of unperformed tasks, emitting information to other agents (vehicles, central depot), and transferring part of the tasks to other participants. With this procedure the occurrence of unperformed tasks at the end of a vehicle cycle-time can be dramatically reduced.

Regarding the transference of pick-up tasks to auxiliary vehicles, two decision rules are contemplated in the analysis: (1) transfer to auxiliary vehicles the visits located at the end of the planned list, and (2) transfer the visits located closest to the centre of mass of all visiting points in the region. The first tactical rule tends to leave additional time to the regular vehicle to perform more tasks, since it tends to decrease its travelled distance. The objective of the second rule is to set up the visits to be performed by the auxiliary vehicle in a closer group, thus reducing its travel time and potentially increasing the number of performed tasks.

A Genetic Algorithm (GA) was developed to set up the dynamic routing of the auxiliary vehicles. A GA chromosome represents the sequentially ordered points (suppliers) to be visited by an auxiliary vehicle, each visiting point being a gene. In the model, there is a chromosome related to each auxiliary vehicle and representing a tentative route, and such a chromosome will vary along the genetic optimisation routine towards the final solution. Along the routing process of the auxiliary vehicles, each chromosome suffers alterations as long as new transferences of pick-up visits occur. New OEM collecting tasks transferred from the regular trucks are added to the auxiliary vehicle routes, while other tasks are removed from the chromosome as soon as the visits are accomplished, thus creating a dynamic routing structure. Whenever the chromosome suffers an alteration, the auxiliary vehicle route is submitted to a re-programming process, i.e. the genetic algorithm performs a new run in order to improve the routing solution.

Larsen (2001) mentions that, when investigating dynamic vehicle routing problems, randomly generated data rather than real-life data are often used. First, the use of randomly generated data often enables more in-depth analyses, since the datasets can be constructed in such a way that other issues could be addressed. Second, the vast majority of real-life dynamic vehicle routing problems do not capture all data needed for in-depth analyses of the specific routing problem. Following this line, a number of variables of probabilistic nature are computed via simulation in this work, to be later used in the general model. The first simulation module is responsible for the scenario settings, including the construction of the routes assigned to the regular vehicles. The focus of the second module is the static version of the system simulation, and the third module is dedicated to the specific dynamic simulation version.

In the model application it is admitted that the logistics operator has agreed to offer an OEM picking-up service to his clients with no more than 2% unperformed collecting tasks. The dynamic setting shows a much better service level when compared with the static version. Furthermore, comparing the dynamic version with one auxiliary vehicle versus the dynamic alternative with two trucks, the latter showed lower level $\rho$ of unperformed tasks, but both presented values of $\rho$ within the predefined service level. But the one auxiliary vehicle alternative showed lower operating costs, being the selected solution to the problem.