Bilevel model for production-distribution planning solved by using ant colony optimization. (English) Zbl 1231.90158

Calvete, Herminia I.; Galé, Carmen; Oliveros, María-José

Comput. Oper. Res. 38, No. 1, 320-327 (2011).

Summary: This paper addresses a hierarchical production-distribution planning problem. There are two different decision makers controlling the production and the distribution processes, respectively, that do not cooperate because of different optimization strategies. The distribution company, which is the leader of the hierarchical process, controls the allocation of retailers to each depot and the routes which serve them. In order to supply items to retailers, the distribution company orders from the manufacturing company the items which have to be available at the depots. The manufacturing company, which is the follower of the hierarchical process, reacts to these orders deciding which manufacturing plants will produce them. A bilevel program is proposed to model the problem and an ant colony optimization based approach is developed to solve the bilevel model. In order to construct a feasible solution, the procedure uses ants to compute the routes of a feasible solution of the associated multi-depot vehicle route problem. Then, under the given data on depot needs, the corresponding production problem of the manufacturing company is solved. Global pheromone trail updating is based on the leader objective function, which involves costs of sending items from depots to retailers and costs of acquiring items from manufacturing plants and unloading them into depots. A computational experiment is carried out to analyze the performance of the algorithm.

© Elsevier Ltd

MSC:

90B30

Production models

Keywords:

bilevel programming; multi-depot vehicle routing problem; ant colony system; production-distribution system

Software:

MDVRPTW

References:

[1]	Ahuja, R. K.; Magnanti, T. L.; Orlin, J. B., Network flows. Theory, algorithms, and applications, 1993, Prentice-Hall: Prentice-Hall Englewood Cliffs, NJ · Zbl 1201.90001
[2]	Anandalingam, G.; Mathieu, R.; Pittard, C. L.; Sinha, N., Artificial intelligence based approaches for solving hierarchical optimization problems, 289-301
[3]	Bard, J. F., Practical bilevel optimization. Algorithms and applications, 1998, Kluwer Academic Publishers: Kluwer Academic Publishers Dordrecht, Boston, London · Zbl 0943.90078
[4]	Bard, J. F.; Moore, J. T., An algorithm for the discrete bilevel programming problem, Naval Research Logistics, 39, 419-435, 1992 · Zbl 0751.90111
[5]	Bell, J. E.; McMullen, P. R., Ant colony optimization techniques for the vehicle routing problem, Advanced Engineering Informatics, 18, 41-48, 2004
[6]	Calvete, H. I.; Galé, C.; Mateo, P., A new approach for solving linear bilevel problems using genetic algorithms, European Journal of Operational Research, 188, 1, 14-28, 2008 · Zbl 1135.90023
[7]	Cao, D.; Chen, M., Capacitated plant selection in a decentralized manufacturing environment: a bilevel optimization approach, European Journal of Operational Research, 169, 1, 97-110, 2006 · Zbl 1077.90555
[8]	Cordeau, J. F.; Gendreau, M.; Laporte, G., A tabu search heuristic for periodic and multi-depot vehicle routing problems, Networks, 30, 105-119, 1997 · Zbl 0885.90037
[9]	Crevier, B.; Cordeau, J. F.; Laporte, G., The multi-depot vehicle routing problem with inter-depot routes, European Journal of Operational Research, 176, 756-773, 2007 · Zbl 1103.90032
[10]	Dempe, S., Foundations of bilevel programming, 2002, Kluwer Academic Publishers: Kluwer Academic Publishers Dordrecht, Boston, London · Zbl 1038.90097
[11]	Dempe, S., Annotated bibliography on bilevel programming and mathematical programs with equilibrium constraints, Optimization, 52, 333-359, 2003 · Zbl 1140.90493
[12]	Dorigo, M.; Gambardella, L. M., Ant colonies for the traveling salesman problem, ByoSystems, 43, 2, 73-81, 1997
[13]	Dorigo, M.; Gambardella, L. M., Ant colony system: a cooperative learning approach to the traveling salesman problem, IEEE Transactions on Evolutionary Computation, 1, 1, 53-66, 1997
[14]	Dorigo, M.; Stützle, T., Ant colony optimization, 2004, MIT Press: MIT Press Cambridge, MA · Zbl 1092.90066
[15]	Edmunds, T. A.; Bard, J. F., An algorithm for the mixed-integer nonlinear bilevel programming problem, Annals of Operations Research, 34, 49-162, 1992 · Zbl 0751.90054
[16]	Erengüc, S. S.; Simpson, N. C.; Vakharia, A. J., Integrated production/distribution planning in supply chains: an invited review, European Journal of Operational Research, 115, 219-236, 1999 · Zbl 0949.90658
[17]	Gendreau, M.; Marcotte, P.; Savard, G., A hybrid tabu-ascent algorithm for the linear bilevel programming problem, Journal of Global Optimization, 9, 1-14, 1996
[18]	Giosa, I.; Tansini, I.; Viera, I., New assignment algorithms for the multi-depot vehicle routing problem, Journal of the Operational Research Society, 53, 984-997, 2002 · Zbl 1079.90030
[19]	Hansen, P.; Jaumard, B.; Savard, G., New branch-and-bound rules for linear bilevel programming, SIAM Journal on Scientific and Statistical Computing, 13, 1194-1217, 1992 · Zbl 0760.65063
[20]	Hejazi, S. R.; Memariani, A.; Jahanshahloo, G.; Sepehri, M. M., Linear bilevel programming solution by genetic algorithm, Computers and Operations Research, 29, 1913-1925, 2002 · Zbl 1259.90120
[21]	Marinakis, Y.; Marinaki, M., A bilevel genetic algorithm for a real life location routing problem, International Journal of Logistics: Research and Applications, 11, 1, 49-65, 2008
[22]	Mathieu, R.; Pittard, L.; Anandalingam, G., Genetic algorithms based approach to bi-level linear programming, RAIRO—Operations Research, 28, 1, 1-22, 1994 · Zbl 0857.90083
[23]	Moore, J. T.; Bard, J. F., The mixed integer linear bilevel programming problem, Operations Research, 38, 5, 911-921, 1990 · Zbl 0723.90090
[24]	Nishizaki, I.; Sakawa, M.; Niwa, K.; Kitaguchi, Y., A computational method using genetic algorithms for obtaining Stackelberg solutions to two-level linear programming problems, Electronics and Communications in Japan, Part 3, 85, 6, 55-62, 2002
[25]	Pisinger, D.; Ropke, S., A general heuristic for vehicle routing problems, Computers and Operations Research, 34, 8, 2403-2435, 2007 · Zbl 1144.90318
[26]	Rajesh, J.; Gupta, K.; Kusumakar, H. S.; Jayaraman, V. K.; Kulkarni, B. D., A tabu search based approach for solving a class of bilevel programming problems in chemical engineering, Journal of Heuristics, 9, 307-319, 2003
[27]	Renaud, J.; Laporte, G.; Boctor, F. F., A tabu-search heuristic for the multi-depot vehicle routing problem, Computers and Operations Research, 23, 3, 229-235, 1996 · Zbl 0855.90055
[28]	Sahin, K. H.; Ciric, A. R., A dual temperature simulated annealing approach for solving bilevel programming problems, Computers and Chemical Engineering, 23, 11-25, 1998
[29]	Tansini, L.; Viera, O., New measures of proximity for the assignment algorithms in the MDVRPTW, Journal of the Operational Research Society, 57, 241-249, 2006 · Zbl 1089.90046
[30]	Vicente, L. N.; Savard, G.; Judice, J., Discrete linear bilevel programming problem, Journal of Optimization Theory and Applications, 89, 3, 597-614, 1996 · Zbl 0851.90084
[31]	Vidal, C. J.; Goetschalckx, M., Strategic production–distribution models: a critical review with emphasis on global supply chain models, European Journal of Operational Research, 98, 1-18, 1997 · Zbl 0922.90062
[32]	Wen, U. P.; Huang, A. D., A simple tabu search method to solve the mixed-integer linear bilevel programming problem, European Journal of Operational Research, 88, 3, 563-571, 1996 · Zbl 0908.90194
[33]	Wen, U. P.; Yang, Y. H., Algorithms for solving the mixed integer two-level linear programming problem, Computers and Operations Research, 17, 2, 133-142, 1990 · Zbl 0683.90055