Multi-atomic Annealing Heuristic for Static Dial-a-ride Problem
  Dial-a-ride problem (DARP) deals with the transportation of users between
pickup and drop-off locations associated with specified time windows. This
paper proposes a novel algorithm called multi-atomic annealing (MATA) to solve
static dial-a-ride problem. Two new local search operators (burn and reform), a
new construction heuristic and two request sequencing mechanisms (Sorted List
and Random List) are developed. Computational experiments conducted on various
standard DARP test instances prove that MATA is an expeditious meta-heuristic
in contrast to other existing methods. In all experiments, MATA demonstrates
the capability to obtain high quality solutions, faster convergence, and
quicker attainment of a first feasible solution. It is observed that MATA
attains a first feasible solution 29.8 to 65.1% faster, and obtains a final
solution that is 3.9 to 5.2% better, when compared to other algorithms within
60 sec.
