PhD thesis Title : Robust optimization approaches for the Inventory Routing Problem
Supervisor name : Bernard Penz
Laboratory supervisor : G-SCOP
Co-Supervisor name : Khaled Hadj Hamou
Doctoral School : IMEP2
Start Date : September-October 2014
Financing – Context – Partnerships :
Keywords
Supervisor name : Bernard Penz
Laboratory supervisor : G-SCOP
Co-Supervisor name : Khaled Hadj Hamou
Doctoral School : IMEP2
Start Date : September-October 2014
Financing – Context – Partnerships :
Keywords
Inventory Routing Problem; Parameter uncertainty;
Robust optimization; Mixed integer programming; Constraint programming
Context
Robust optimization; Mixed integer programming; Constraint programming
Context
In the current business environment logistics is one of the key elements to gain a
competitive advantage over the direct competitors.Recently, vendor-managed inventory
(VMI) systems have emerged as an important component in the logistic strategies.
In this business model the supplier takes responsibility for the inventory of the client
until the moment of use. Both supplier and client benefit from this practice. The client
doesn’t have to put effort into monitoring and maintaining his inventory. The supplier
can combine deliveries to multiple clients more effectively and thus save distribution
costs. The well-known Inventory Routing Problems (IRP) aims at integrating routing
problems and inventory management models.
competitive advantage over the direct competitors.Recently, vendor-managed inventory
(VMI) systems have emerged as an important component in the logistic strategies.
In this business model the supplier takes responsibility for the inventory of the client
until the moment of use. Both supplier and client benefit from this practice. The client
doesn’t have to put effort into monitoring and maintaining his inventory. The supplier
can combine deliveries to multiple clients more effectively and thus save distribution
costs. The well-known Inventory Routing Problems (IRP) aims at integrating routing
problems and inventory management models.
Proposal
To model VMI systems Inventory Routing Problems (IRP) have been proposed. These models minimize inventory costs for both the supplier and the clients and the transportation costs between supplier and clients. A lot of research has been done on IRP (Coelho, 2014). However, most of these models assume predictable travel times and associated costs. In real life this is usually not the case.
To overcome the gap between theoretical models and reality this thesis project proposes to include variability on both costs and travel times in the IRP model.
As a result of the introduced variability the optimal solution of the nominal problem (without variability) may produce very different, sub-optimal, results under various circumstances. Next to the potential suffering of enormous variability in the results, the solution of the nominal problem might even become infeasible for certain scenarios.
In this context robust optimization arises. The goal of robust optimization is to optimize the mean while minimizing the variability that results from uncertainty. For this purpose the problem will first have to be reformulated. In a second phase appropriate solution methods for the robust problem can be found and modified. Methods such as Mixed Integer Programming and constraint programming can be used for this purpose.
A complicating factor in this second phase is the NP-completeness of the IRP. Since the robust problem envelops the nominal problem, the former will also be NP-complete. Therefore, large instances might require exponential calculation time to solve to optimality. Due to the NP-completeness of the problem, the exact methods described in the previous paragraph may not longer be interesting. It can be more opportune to address the problem with heuristic methods and approximation algorithms.
After finding an optimal or nearly optimal solution for the problem, a new problem arises namely finding an accurate estimate of the associated cost of this solution. The variability on the parameters of the model will induce a variability on the cost of the solution, leading to the cost having a certain distribution.
Expected work plan
Step 1: Literature review
To model VMI systems Inventory Routing Problems (IRP) have been proposed. These models minimize inventory costs for both the supplier and the clients and the transportation costs between supplier and clients. A lot of research has been done on IRP (Coelho, 2014). However, most of these models assume predictable travel times and associated costs. In real life this is usually not the case.
To overcome the gap between theoretical models and reality this thesis project proposes to include variability on both costs and travel times in the IRP model.
As a result of the introduced variability the optimal solution of the nominal problem (without variability) may produce very different, sub-optimal, results under various circumstances. Next to the potential suffering of enormous variability in the results, the solution of the nominal problem might even become infeasible for certain scenarios.
In this context robust optimization arises. The goal of robust optimization is to optimize the mean while minimizing the variability that results from uncertainty. For this purpose the problem will first have to be reformulated. In a second phase appropriate solution methods for the robust problem can be found and modified. Methods such as Mixed Integer Programming and constraint programming can be used for this purpose.
A complicating factor in this second phase is the NP-completeness of the IRP. Since the robust problem envelops the nominal problem, the former will also be NP-complete. Therefore, large instances might require exponential calculation time to solve to optimality. Due to the NP-completeness of the problem, the exact methods described in the previous paragraph may not longer be interesting. It can be more opportune to address the problem with heuristic methods and approximation algorithms.
After finding an optimal or nearly optimal solution for the problem, a new problem arises namely finding an accurate estimate of the associated cost of this solution. The variability on the parameters of the model will induce a variability on the cost of the solution, leading to the cost having a certain distribution.
Expected work plan
Step 1: Literature review
- present and discuss the IRP model and algorithms for its solutions
- present and discuss robust optimization approaches
Step2: Optimization model reformulation
- propose appropriate model reformulations to address parameter variability's
Step 3: Model solving
- propose appropriate algorithms to solve resulting robust optimization models
Step 4: Implementation and tests
Contact(s) : Bernard.penz@grenoble-inp.fr ; Khaled.hadj-hamou@grenoble-inp.fr
Contact(s) : Bernard.penz@grenoble-inp.fr ; Khaled.hadj-hamou@grenoble-inp.fr