Itinerary optimization approach inside hypermarkets

Itinerary optimization approach inside hypermarkets

Ismahène Hadj Khalifa
Abdelkader El Kamel

Institut Supérieur des Arts de Multimédia Université de la Mannouba, 2010, Manouba, Tunisie

Ecole Centrale de Lille BP 48, 59651 Villeneuve d’Ascq, France

Corresponding Author Email: 
ismahenhk@yahoo.fr
Page: 
31-53
|
DOI: 
https://doi.org/10.3166/JESA.49.31-53
Received: 
13/03/2012
| |
Accepted: 
26/11/2015
| | Citation

OPEN ACCESS

Abstract: 

In this paper, we concentrate on the hypermarket itinerary optimization. We propose a methodology to calculate the distance between each two items in the hypermarket before implementing the optimization algorithm, to estimate the shortest path to pick up the items existing in the shopping list.

Keywords: 

indoor navigation system, path optimization Christofides algorithm modified, Nearest Neighbor algorithm adapted, tabou search method with sets.

1. Introduction
2. État de l’art sur les méthodes d’optimisation d’itinéraire en temps réel
3. Proposition d’une méthode d’optimisation d’itinéraire dans un hypermarché
4. Approches d’optimisation de l’itinéraire dans un hypermarché
5. Étude expérimentale et résultats
6. Contributions et conclusion
  References

Applegate D, Bixby RE, Chvatal V, Cook W. (2007). The Traveling Salesman Problem: a Computational Study, Princeton University Press, Princeton.

Abboud M., Abou Jaoude L.M., Kerbage Z. (2004). Real Time GPS Navigation System, http://webfea-lb.fea.aub.edu.lb/proceedings/2004/SRC-ECE-27.pdf

Avella P., Boccia M., Sforza A. (2004). Solving a fuel delivery problem by heuristic and exact approaches, European Journal of Operational Research, vol. 152, n° 1, p. 170-179.

Bianchi L. (2000). Notes on Dynamic Vehicle Routing - The State of the Art. Technical Report, IDSIA-05-01.

Christofides N. (1976). Worst-case analysis of a new heuristic for the travelling salesman problem. Report 388, Graduate School of Industrial Administration, CM.

Gendreau M., Guertin F., Potvin J.-Y., Séguin R (1998). Neighborhood search heuristics for a dynamic vehicle dispatching problem with pick-ups and deliveries. Technical Report, CRT-98-10, Centre de Recherche sur les Transports, Université de Montréal.

Gendreau M., Hertz A., Laporte G. (1994). A tabu search heuristic for the vehicle routing problem, Management Science, 40, p. 1276-1290.

Glover F. (1989). Tabu Search—Part I, ORSA Journal on Computing 1, p. 190-206.

Glover F. (1990). Tabu Search—Part II, ORSA Journal on Computing 2, p. 4-32.

Glover F.,Taillard E., Werra D. (1993). A user’s guide to tabu search, Annals of Operations Research, 41, p. 3-28.

Hadj Khalifa I., El Kamel A., Barfety B. (2010). Optimisation de parcours en temps réel dans un hypermarché, ROADEF 2010, Toulouse, France.

Hadj Khalifa I. El Kamel A., Barfety B. (2010). Real time indoor intelligent navigation system inside hypermarkets, Large Scale Systems: Theory and Applications, LSS2010, Lille, France.

Held M., Karp R.M (1969). The Traveling Salesman Problem and Minimal Spanning Trees, Operations Research 18, p. 113.

Housroum H., Goncalves G., Dupas R., Hsu T. (2004). An hybrid GA approach for solving the Dynamic Vehicle Routing Problem with Time Windows, Francoro IV, Fribourg, Suisse.

Johnson D.S., McGeoch L.A. (2002). Experimental Analysis of Heuristics for the STSP, The Traveling Salesman Problem and its Variations, Gutin and Punnen (eds), Kluwer Academic Publishers, p. 369-443.

Kilby P., P. Prosser, et P. Shaw (1998). Dynamic VRPs: A Study of Scenarios, CSIRO, Canberra ACT 2601, Australia.

Lacomme P., Prins C., Sevaux M. (2003). Algorithmes de graphes, Eyrolles 2e édition.

Laporte E G. (1992). The traveling salesman problem: An overview of exact and approximate algorithms. European Journal of Operational Research, 59, p. 231-247

Larsen A (2001). The Dynamic Vehicle Routing Problem. Thèse de doctorat, IMM, Technical University of Denmar.

Larsen A., Madsen O.B.G., Solomon M. (2002). Partially Dynamic Vehicle Routing – Models and Algorithms, Journal of the Operational Research Society, p. 637-646.

Montamenni R., Gambardella L.M., Rizzoli A.E., Donati A.V. (2002). A new algorithm for a Dynamic Vehicle Routing Problem based on Ant Colony System, IDSIA, Switzerland.

Pérez-Ponce H., P.R. Hernandez-Rodriguez (2004). Navigation system for visual impaired persons based on satellital location, Proceedings of the 26th Annual International Conference of the IEEE EMBS San Francisco, CA, USA.

Pillac V., Gendreau M., Guéret C., Medaglia A.L. (2013). A review of dynamic vehicle routing problems. European Journal of Operational Resear, vol. 225, p. 1-11

Ravi R., Goemans M.X. (1996). The constrained minimum spanning tree problem, Proceedings of the Scandinavian Workshop on Algorithm Theory, Lecture Notes on Computer Science, vol. 1097, p. 66-75

Roy S.,J.-M. Rousseau, G. Lapalme, Ferland J. A. (1984). Routing and scheduling of transportation services for disabled: summary report. Technical report, Centre de recherche sur les transports, Université de Montréal.