Курсы английского
<<  Finding Application Errors and Security Flaws Using PQL: A Program Query Language Z-MAC: Hybrid MAC for Wireless Sensor Networks  >>
A hybrid heuristic for an inventory routing problem
A hybrid heuristic for an inventory routing problem
The literature
The literature
The literature
The literature
The literature
The literature
The problem
The problem
Replenishment policies
Replenishment policies
Order-Up-to level policy (OU)
Order-Up-to level policy (OU)
The Maximum Level policy (ML)
The Maximum Level policy (ML)
Basic decision variables
Basic decision variables
Problem formulation
Problem formulation
Inventory definition at the customers
Inventory definition at the customers
Order-up-to level constraints
Order-up-to level constraints
Routing constraints
Routing constraints
Known algorithms
Known algorithms
History of the hybrid heuristic design
History of the hybrid heuristic design
HAIR (Hybrid Algorithm for Inventory Routing)
HAIR (Hybrid Algorithm for Inventory Routing)
OU policy - Initialize
OU policy - Initialize
OU policy – Tabu search
OU policy – Tabu search
OU policy – Improvements – MILP 1
OU policy – Improvements – MILP 1
OU policy – Improvements – MILP 1
OU policy – Improvements – MILP 1
OU policy – Improvements – MILP 1
OU policy – Improvements – MILP 1
OU policy – Improvements – MILP 1
OU policy – Improvements – MILP 1
OU policy – Improvements – MILP 2
OU policy – Improvements – MILP 2
OU policy – Improvements – MILP 2
OU policy – Improvements – MILP 2
OU policy – Improvements – MILP 2
OU policy – Improvements – MILP 2
OU policy - Jump
OU policy - Jump
The hybrid heuristic for the ML policy
The hybrid heuristic for the ML policy
Tested instances
Tested instances
Summary of results
Summary of results
Summary of results
Summary of results
Summary of results
Summary of results
Large instances
Large instances
Summary of results – large instances
Summary of results – large instances
Summary of results – large instances
Summary of results – large instances
Hybrid vs tabu – OU policy
Hybrid vs tabu – OU policy
Hybrid vs tabu – ML policy
Hybrid vs tabu – ML policy
Conclusions
Conclusions

Презентация: «A hybrid heuristic for an inventory routing problem». Автор: . Файл: «A hybrid heuristic for an inventory routing problem.ppt». Размер zip-архива: 142 КБ.

A hybrid heuristic for an inventory routing problem

содержание презентации «A hybrid heuristic for an inventory routing problem.ppt»
СлайдТекст
1 A hybrid heuristic for an inventory routing problem

A hybrid heuristic for an inventory routing problem

C.Archetti, L.Bertazzi, M.G. Speranza University of Brescia, Italy A.Hertz Ecole Polytechnique and GERAD, Montr?al, Canada

DOMinant 2009, Molde, September 20-23

2 The literature

The literature

Surveys Federgruen, Simchi-Levi (1995), in ‘Handbooks in Operations Research and Management Science’ Campbell et al (1998), in ‘Fleet Management and Logistics’ Cordeau et al (2007) in ‘Handbooks in Operations Research and Management Science: Transportation’ Bertazzi, Savelsbergh, Speranza (2008) in ‘The vehicle routing problem...’, Golden, Raghavan, Wasil (eds) Pioneering papers Bell et al (1983), Interfaces Federgruen, Zipkin (1984), Operations Research Golden, Assad, Dahl (1984), Large Scale Systems Blumenfeld et al (1985), Transportation Research B Dror, Ball, Golden (1985), Annals of Operations Research ……

3 The literature

The literature

Deterministic product usage - no inventory holding costs in the objective function Jaillet et al (2002), Transp. Sci. Campbell, Savelsbergh (2004), Transp. Sci. Gaur, Fisher (2004), Operations Research Savelsbergh, Song (2006), Computers and Operations Research …… Deterministic product usage - inventory holding costs in the objective function Anily, Federgruen (1990), Management Sci. Speranza, Ukovich (1994), Operations Research Chan, Simchi-Levi (1998), Management Sci. Bertazzi, Paletta, Speranza (2002), Transp. Sci. Archetti et al (2007), Transp. Sci. ……

4 The literature

The literature

Deterministic product usage - inventory holding costs in the objective function – production decision Bertazzi, Paletta, Speranza (2005), Journal of Heuristics Archetti, Bertazzi, Paletta, Speranza , forthcoming Boudia, Louly, Prins (2007), Computers and Operations Research Boudia, Prins (2007), EJOR Boudia, Louly, Prins (2008), Production Planning and Control

5 The problem

The problem

Data

Availability at t

Demand of s at t

Capacity of s

+ initial inventory + travelling costs + inventory costs + vehicle capacity

n customers H time units 1 vehicle

How much to deliver to s at time t to minimize routing costs + inventory costs

No stock-out No lost sales

1

0

2

3

6 Replenishment policies

Replenishment policies

Order-Up-to Level (OU) Maximum Level (ML)

Constraints on the quantities to deliver

1

0

2

3

7 Order-Up-to level policy (OU)

Order-Up-to level policy (OU)

Inventory at customer s

Maximum level

Us

Initial level

Time

8 The Maximum Level policy (ML)

The Maximum Level policy (ML)

Every time a customer is visited, the shipping quantity is such that at most the maximum level is reached

Us

9 Basic decision variables

Basic decision variables

10 Problem formulation

Problem formulation

Inventory definition at the supplier

Stock-out constraints at the supplier

11 Inventory definition at the customers

Inventory definition at the customers

Stock-out constraints at the customers

Capacity constraints

12 Order-up-to level constraints

Order-up-to level constraints

The quantity shipped to s at time t is

Maximum level constraints

13 Routing constraints

Routing constraints

14 Known algorithms

Known algorithms

A branch-and-cut algorithm (for the OU and for the ML policies) Archetti, Bertazzi, Laporte, Speranza (2007), Transp. Science

A heuristic (for the OU policy) Bertazzi, Paletta, Speranza (2002), Transp. Science

Local search Very fast Error?

Instances up to H=3, n=50 H=6, n=30

15 History of the hybrid heuristic design

History of the hybrid heuristic design

Exact approach allowed us to compute errors generated by the local search Design of a tabu search Design of a hybrid heuristic (tabu search +MILP models)

Often large errors, rarely optimal Sometimes large errors, sometimes optimal Excellent results

16 HAIR (Hybrid Algorithm for Inventory Routing)

HAIR (Hybrid Algorithm for Inventory Routing)

Initialize generates initial solution A Tabu search is run Whenever a new best solution is found Improvements is run Every JumpIter iterations without improvements Jump is run

17 OU policy - Initialize

OU policy - Initialize

Each customer is served as late as possible

Initial solution may be infeasible (violation of vehicle capacity or stock-out at the supplier)

18 OU policy – Tabu search

OU policy – Tabu search

Search space: feasible solutions infeasible solutions (violation of vehicle capacity or stock-out at the supplier) Solution value: total cost + two penalty terms Moves for each customer: Removal of a day Move of a day Insertion of a day Swap with another customer After the moves: Reduce infeasibility Reduce costs

19 OU policy – Improvements – MILP 1

OU policy – Improvements – MILP 1

Route assignment Goal: to find an optimal assignment of routes to days optimizing the quantities delivered at the same time. Removal of customers is allowed.

Optimal solution of a MILP model

20 OU policy – Improvements – MILP 1

OU policy – Improvements – MILP 1

The route assignment model

Binary variables: assignment of route r to time t removal of customer s from route r Continuous variables: quantity to customer s at time t inventory level of customer s at time t inventory level of the supplier at time t

21 OU policy – Improvements – MILP 1

OU policy – Improvements – MILP 1

The route assignment model

NP-hard

Min inventory costs – saving for removals s.t. Stock-out constraints OU policy defining constraints Vehicle capacity constraints Each route can be assigned to one day at most Technical constraints on possibility to serve or remove a customer

# of binary variables: (n+H)*(# of routes)+n*H

22 OU policy – Improvements – MILP 1

OU policy – Improvements – MILP 1

Day 5

Day 6

Day 1

Day 2

Day 3

Day 4

Incumbent solution

The optimal route assignment

Node removed

Unused

23 OU policy – Improvements – MILP 2

OU policy – Improvements – MILP 2

Customer assignment Objective: to improve the incumbent solution by merging a pair of consecutive routes. Removal of customers from routes, insertion of customers into routes and quantities delivered are optimized.

Optimal solution of a MILP model

For each merging and possible assignment day of the merged route a MILP is solved

24 OU policy – Improvements – MILP 2

OU policy – Improvements – MILP 2

The customer assignment model

Binary variables: removal of customer s from time t insertion of customer s into time t Continuous variables: quantity to customer s at time t inventory level of customer s at time t inventory level of the supplier at time t

25 OU policy – Improvements – MILP 2

OU policy – Improvements – MILP 2

The customer assignment model

NP-hard

Min inventory costs + insertion costs – saving for removals s.t. Stock-out constraints OU policy defining constraints Vehicle capacity constraints Each route can be assigned to one day at most Technical constraints on possibility to insert or remove a customer

# of binary variables: n*H

26 OU policy - Jump

OU policy - Jump

After a certain number of iterations without improvements a jump is made. Jump: move customers from days where they are typically visited to days where they are typically not visited. (In our experiments a jump is made only once)

27 The hybrid heuristic for the ML policy

The hybrid heuristic for the ML policy

The ML policy is more flexible than the OU policy

The entire hybrid heuristic has been adapted

28 Tested instances

Tested instances

160 benchmark instances from Archetti et al (2007), TS Known optimal solution H = 3, n = 5,10, …., 50 H = 6, n = 5,10, …., 30 Inventory costs low, high

29 Summary of results

Summary of results

30 Summary of results

Summary of results

31 Summary of results

Summary of results

32 Large instances

Large instances

Optimal solution unknown

H = 6 n = 50, 100, 200 Inventory costs: low, high 10 instances for each size for a total of 60 instances

HAIR has been slightly changed: the improvement procedure is called only if at least 20 iterations were performed since its last application; the swap move is not considered.

33 Summary of results – large instances

Summary of results – large instances

Running time for OU: 1 hour Running time for ML: 30 min Errors taken with respect to the best solution found Running time BPS: always less than 3 min

34 Summary of results – large instances

Summary of results – large instances

Running time for OU: 1 hour Running time for ML: 30 min Errors taken with respect to the best solution found Running time BPS: always less than 3 min

35 Hybrid vs tabu – OU policy

Hybrid vs tabu – OU policy

36 Hybrid vs tabu – ML policy

Hybrid vs tabu – ML policy

37 Conclusions

Conclusions

Tabu search combined with MILP models very successful Use of the power of CPLEX Ad hoc designed MILP models used to explore in depth parts of the solution space It is crucial to find the appropriate MILP models (models that are needed, models that explore promising parts of the solution space, trade-off between size of search and complexity)

«A hybrid heuristic for an inventory routing problem»
http://900igr.net/prezentacija/anglijskij-jazyk/a-hybrid-heuristic-for-an-inventory-routing-problem-107955.html
cсылка на страницу
Урок

Английский язык

29 тем
Слайды