GRASP Initialization Stage for Bus-Network Hybrid Algorithm

OLIVERA A.C.; FRUTOS M.; CARBALLIDO J.A.; BRIGNOLE N.B.

Mar del Plata, Buenos Aires, Argentina

Congreso; 36 JAIIO: 36th Conference on Computer Science and Operational Research-; 2007

This work presents the initialization stage of a time-dependent hybridalgorithm for the optimization of the bus-network scheduling problem (BNSP).The BNSP is NP-Complete and the mathematical techniques for their resolutionsuffer difficulties in realistic sceneries. Several authors propose heuristicsalternatives for the BNSP. The hybrid approach exposed in this work consistsof two stages: an initialization stage and a genetic stage. The objective is toprovide an effective computational tool for large-scale BNSP. GreedyRandomized Adaptive Search Procedures (GRASP) is the combinatorialoptimization meta-heuristics chosen for the initialization of the distancebetween bus stops. This paper focuses in the initialization GRASP stage, itsimplementation and results.