# Opportunistic and Dynamic Reconfiguration of Vehicle Routing Problem Controlled by the Intelligent Product

Rodrigue Tchapnga Takoudjou, Jean-Christophe Deschamps, Rémy Dupas

► To cite this version:

Rodrigue Tchapnga Takoudjou, Jean-Christophe Deschamps, Rémy Dupas. Opportunistic and Dynamic Reconfiguration of Vehicle Routing Problem Controlled by the Intelligent Product. 19th Advances in Production Management Systems (APMS), Sep 2012, Rhodes, Greece. pp.608-613, 10.1007/978-3-642-40361-3_77. hal-01470674

HAL Id: hal-01470674

https://inria.hal.science/hal-01470674

Submitted on 17 Feb 2017

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
Opportunistic and Dynamic Reconfiguration of Vehicle
Routing Problem Controlled by the Intelligent Product

Rodrigue Tchapnga Takoudjou<fnref n="1" />, <fnref n="2" /> Jean-Christophe Deschamps<fnref n="1" />, <fnref n="2" />
Rémy Dupas<fnref n="1" />, <fnref n="2" />

{rodrigue.tchapnga-takoudjou, Jean-Christophe.Deschamps,
remy.dupas}@ims.bordeaux.fr

**Abstract.** The recent development of information technologies and communications as well as the miniaturization always more pushed of mecatronic components has allowed the emergence of intelligent product paradigm. An intelligent product is an instrumented product which is able to store data, to perceive its environment and to participate in decisions about its own future. The intelligent product paradigm can be used as performance lever in several sectors of the supply chain: the production and manufacturing system, warehousing, reverse logistics, etc. However, few studies exist for the application of the intelligent product paradigm to transportation problem. In this paper, we propose a methodology based on the intelligent product paradigm as well as the shipment with the aim to show how we can improve, and optimize the transport of products in the supply chain in static or dynamic context.

**Keywords:** Intelligent Product, Vehicle Routing Problem, Heuristics, Transshipment.

# 1 Introduction

The role of transport in the economy is not any more to demonstrate. It plays a sig-
nificant role in the performance of the supply chain. Because of globalization, trans-
portation has become a more and more complex operation and presents many chal-
lenges. Indeed, the diversification of supply sources, the emergence of the practices
such as the cross-dock, as well as resources sharing in the transport raises problems of
intermediate reloading, and of synchronization in the transport, etc.

Because of these new practices, besides the classic problem of optimization of the
costs of the transport, new problems have appeared. We can mention the problem of
traceability (break of the cold chain), the calculation of the carbon footprint of a prod-
uct, the lack of synchronization between the physical flow and the informational flow
of a product (the vehicle is tracked but not the product), the lack of anticipation and
responsiveness of the transportation system following the occurrence of an event, etc.

<footnote n="1">¹ Univ. Bordeaux, IMS, UMR 5218, F-33400 Talence, France.</footnote>

<footnote n="2">²CNRS, IMS, UMR 5218, F-33400 Talence, France.</footnote>
To solve these problems, we propose two action levers. The first one whom we propose is the transshipment. It allows optimizing the cost of collection and distribution of the product in terms of number of vehicles used and total travelled distances. The second is a distributed architecture for the control of the transportation system, based on the instrumentation of the product and of the transportation in general. The aim is to propose a new control system which ensures the flexibility, robustness of the transport, and which facilitates the alignment of the informational and the physical flow for a real-time control of the transport. The expected result by the combination of these two action levers is to guarantee an overall performance of the transport of products.

## 2 Related Work

The rapid development of new technologies and the miniaturization of mechatronic component have allowed the emergence of the intelligent products. A recent state of the art on intelligent product paradigm as well as on its various applications on the supply chain is proposed in [1]. Among the most notable work, we can mention: the steering of the workshop by the product [2], the improvement of the management of warehouses on the basis of the use of RFID technology [3], etc. Concerning the transport, few works exist on the active or passive participation of the product in the decisions relative to its transport. One of work published on the domain is the paper [4] in which authors propose solutions facilitating the interoperability in the transport within the framework of international projects.

Concerning the transshipment, it offers the possibility to deliver a product through two vehicles at least. For instance, one vehicle picks up a load at the supplier location, drops it at a transshipment point with short storage and another vehicle carries and delivers this load to the final destination. In [5] authors propose a heuristics to solve the pickup and delivery problem with time window and transshipment (PDPT). In the literature, to author's knowledge, there is no heuristics which allows solving the PDPT in real time in which the product is active in the process of decision which concerns its transport.

## 3 The Pickup and Delivery Problem with Transshipment

The principle of opportunistic transshipment provides the ability for the product to use more than one vehicle before being delivered to the customer. To illustrate the advantage to practice transshipment in transportation, we provide the following example: In figure 1, two vehicles are in charge of the collection and the delivery of four products. Product "J" is to be loaded at PJ and delivered at DJ ($1 \le J \le 4$). If transshipment is not allowed, to delivered all the products, vehicle 1 will follow the trajectory P1, P2, D1, D2 and vehicle 2 will follow the trajectory P3, P4, D4, D3. The total distance travelled by the two vehicles is 19. If transshipment is authorized, vehicle 1 will follow trajectory P3, P4, T, D1, D3 and vehicle 2 will follow the trajectory P1, P2, T,
D2, D4. The total distance travelled by the two vehicles in this case is 16. In this solution after loading product 1 and product 2 at P1 and P2, product 1 is dropped by vehicle 1 at T. After loading product 3 and 4 at P3 and P4, product 4 is dropped by vehicle 2 at T. Then, vehicle 1 reloads product 4 at T and respectively delivery product 2(4) at D2 (D4). Vehicle 2 reload product 1 at T and respectively deliver 1(3) at D1 (D3). In conclusion, for the total distance travelled, transshipment yields net saving of 16%.

<figure><img src="image_2.png" /><figcaption>**Fig. 1.** Graphical representation of the problem (requests are represented by the dotted arcs)</figcaption></figure>

To solve the PDPT in real time context, we have adapted the heuristic we have developed in [6] for the static case. The developed solving approach is used in a real time context; that is to say that the vehicles are moving on their routes to the customers. Position of each truck, its residual capacity and condition of products it carries are supposed to be precisely known. The overall visibility of the transportation situation allows in case of occurrence of a disturbance to quickly identify the consequence in terms of compliance of routing constraints. When a delay is observed, leading a vehicle to not respect all rendezvous with customers, the best suited vehicle is identified for recover the products of the vehicle which raise the disturbance. The real technical complexity of the proposed approach then lies in updating the graph which characterizes the transport network. Indeed, depending on the evolution of the transport situation, the customers whose demands are satisfied are removed from the graph, and the current position of the truck is considered as a new vertex of the graph. Due to lack of space, a detailed overview of the heuristic will be provided during the conference.

# 4 Instrumentation of the Transport

The instrumentation of the transport (figure 2) consists by means of the technology, to confer to every actor of the transport a degree of intelligence characterized by a
set of properties such as memorization, perception of its environment, communication and the decision capacity. The main actors of the transport are the products (pallets and trailers), the tractor or lorry (in charge of moving trailers), customers and the transport operator that owns the vehicles fleet. To obtain in real time a permanent and continuous global vision of the transportation system, it is necessary to effectively trace and locate the products and the vehicles in real time. This supposes to have a continuous information flow issued from the product which can be described briefly in the following way: each product is tagged with an RFID chip. The chip integrates sensors and can store information. By this mechanism, the product becomes commu- nicant. Information exchanges take place between products and a RFID reader placed in the trailer. The RFID reader in the trailer permanently scans information stored in the products. The Reader is connected to an embedded computer (smart phone) placed in the tractor cabin. The embedded terminal integrates a GPS chip to allow the locali- zation of the vehicle and by deduction, the localization of the product. The infor- mation collected in real time by the computer is locally exploited by the vehicle to reconfigure its route, or there are sent by mobile phone to a decision maker. Once the instrumentation process of the product and of the transport has been described, we now propose a hybrid architecture that can support the distribution of the intelligence. To have a fine and global information of the situation of the transport, in addition to the instrumentation of the actors, there are two families (C1 and C2) of control points: C1 (with timestamp) - these points correspond to the visit by the truck of every cus- tomer of its route. C2 (with variable location) - these points correspond to a periodic acquisition (by geo-localization) of the vehicle's position during its movement.

<figure><img src="image_3.png" /><figcaption>Fig. 2. The information chain</figcaption></figure>

4.1 A distributed and decision architecture for transportation systems

By considering this technical implementation, the proposed architecture of the transport system is hybrid (fig. 3). It combines the strengths of centralized and hierar- chical control systems. Every product is tagged with an RFID chip which allows it to communicate with the truck which transports it. Each truck is equipped with an onboard computer in which are implemented the algorithms of calculations (heuristics and exact model) which allow the reconfiguration of its route due to the occurrence of
a disturbance. Following the occurrence of a disturbance, the routes of vehicles situat-
ed in the perimeter of the disturbance are reconfigured. The reconfiguration is based
on the transshipment and is made in the form of a dialogue and in a collective way
between the concerned vehicles. The distribution of the algorithms of calculation
towards vehicles is made in a concern of reactivity and efficiency. Indeed, the context
of every disturbance is clearly establishes in real time and the precise and targeted
actions are activated to bring a correction. However, this distribution of the calcula-
tion may result in a closed-optimal solution in term of cost (but not an optimal solu-
tion); what is not a handicap in the case of our application. If no action emerges from
negotiations between vehicles, the server acts as an arbitrator and provides a solution
(control).

<figure><img src="image_4.png" /><figcaption>Fig. 3. Architecture of the transport system</figcaption></figure>

## 4.2 Scenario of the Control of the Transport by The Product

A scenario of transport in which products as well as trucks are instrumented ac-
cording to the process described in the previous section will be described here in the
final version of the paper.
# 5 Conclusion

In this paper, we have worked on an opportunistic and dynamic reconfiguration of vehicle routing problem controlled by the Intelligent Product. We have shown how the global performance of the transport can be improved on several points:

* Reactivity - the disturbances are detected in real time, with a specific context. This property allows establishing an accurate correction through the distribution of intelligence between vehicles.

* Synchronization between the physical flow (the product) and the flow of information flow - the product being the carrier of its own information, this synchronization is achieved. The instrumentation of the transport such as recommended is a vector of improvement of performances in this domain.

In the following of this work, the solution proposed in a methodological way in this paper will be implemented and tested on a real case within the framework of a project<fnref n="1" />.

# Acknowledgments

This research has been supported by ANR under the grant VTT-PRODIGE (ANR-09-VTT-09-01) and is labeled by NOVALOG.

# References

1. Meyer, G.G., K. Främling, and J. Holmström, *Intelligent Products: A survey*. Computers in Industry, 2009. **60**(3): p. 137-148.

2. McFarlane, D., et al., *Auto ID systems and intelligent manufacturing control*. Engineering Applications of Artificial Intelligence, 2003. **16**(4): p. 365-376.

3. Xu, J., et al., *Comparing improvement strategies for inventory inaccuracy in a two-echelon supply chain*. European Journal of Operational Research, 2012. **221**(1): p. 213-221.

4. Kärkkäinen, M., et al., *Intelligent products—a step towards a more effective project delivery chain*. Computers in Industry, 2003. **50**(2): p. 141-151.

5. S. Mitrović-Minić and G. Laporte, *The pickup and delivery problem with time windows and transshipment*. INFOR, 2006. **44**(3): p. 217-227.

6. Tchapnga R., D.J.-C., Dupas R., *An hybrid Multistart Heuristic for the Pickup and Delivery Problem with and without Transhipment*, in 9th International Conference of Modeling, Optimization and Simulation (MOSIM'12), Bordeaux (France). 2012.

<footnote n="1">¹ French project named PRODIGE (ANR - VTT 2009) funded by the French national research agency (ANR). http://anr-prodige.com/</footnote>