GRASP initialization stage for bus-network hybrid algorithm

OLIVERA ANA CAROLINA; FRUTOS MARIANO; CARBALLIDO, JESSICA ANDREA; BRIGNOLE, NÉLIDA BEATRIZ

Mar del Plata, Argentina

Simposio; SIO 2007 (Simposio de Investigación Operativa - JAIIO 2007); 2007

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.