Parallelization of a Two-Phase Metaheuristic for Routing Problems with Time Windows

This paper describes the parallelization of a two-phase metaheuristic for the vehicle routing problem with time windows and a central depot (VRPTW). The underlying objective function combines the minimization of the number of vehicles in the first search phase of the metaheuristic with the minimization of the total travel distance in the second search phase. The parallelization of the metaheuristic follows a type 3 parallelization strategy (cf. Crainic and Toulouse (2001). In F. Glover and G. Kochenberger (eds.). State-of-the-Art Handbook in Metaheuristics. Norwell, MA: Kluwer Academic Publishers), i.e. several concurrent searches of the solution space are carried out with a differently configured metaheuristic. The concurrently executed processes cooperate through the exchange of solutions. The parallelized two-phase metaheuristic was subjected to a comparative test on the basis of 358 problems from the literature with sizes varying from 100 to 1000 customers. The derived results seem to justify the proposed parallelization concept.     

The numerical treatment of perturbed bifurcation problems in ordinary differential equations

A new numerical method is presented to analyze perturbations of bifurcations of the solutions of nonlinear boundary value problems. The perturbations may result from imperfections or other inhomogeneities in the corresponding scientific problem. The nonisolated solutions are calculated in dependence of the perturbation parameter. Therefore, it is possible to determine the singular solution as well as a solution branch through this nonisolated solution simultaneously. Standard procedures of numerical analysis are applicable.