GRASP initialization stage for bus-network hybrid algorithm

ANA C. OLIVERA; MARIANO FRUTOS; JESSICA A. CARBALLIDO; NÉLIDA B.BRIGNOLE

Mar del Plata, Buenos Aires, Argentina

Simposio; Simposio de Investigación Operativa SIO 2007 ((JAIIO Jonadas Argentinas de Informática e Investigación Operativa)); 2007

Sociedad Argentina de Informática

 This work presents the initialization stage of a time-dependent hybrid algorithm for the optimization of the bus-network scheduling problem (BNSP). The BNSP is NP-Complete and the mathematical techniques for their resolution suffer difficulties in realistic sceneries. Several authors propose heuristics alternatives for the BNSP. The hybrid approach exposed in this work consists of two stages: an initialization stage and a genetic stage. The objective is to provide an effective computational tool for large-scale BNSP. Greedy Randomized Adaptive Search Procedures (GRASP) is the combinatorial optimization meta-heuristics chosen for the initialization of the distance between bus stops. This paper focuses in the initialization GRASP stage, its implementation and results.