Genetic scatter search algorithm to solve the one-commodity pickup and delivery vehicle routing problem

Abstract

Purpose

In this paper, the author introduces a new variant of the pickup and delivery transportation problem, where one commodity is collected from many pickup locations to be delivered to many delivery locations within pre-specified time windows (one–to many–to many). The author denotes to this new variant as the 1-commodity pickup-and-delivery vehicle routing problem with soft time windows (1-PDVRPTW).

Design/methodology/approach

The author proposes a hybrid genetic algorithm and a scatter search to solve the 1-PDVRPTW. It proposes a new constructive heuristic to generate the initial population solution and a scatter search (SS) after the crossover and mutation operators as a local search. The hybrid genetic scatter search replaces two steps in SS with crossover and mutation, respectively.

Findings

So, the author proposes a greedy local search algorithm as a metaheuristic to solve the 1-PDVRPTW. Then, the author proposes to hybridize the metaheuristic to solve this variant and to make a good comparison with solutions presented in the literature.

Originality/value

The author considers that this is the first application in one commodity. The solution methodology based on scatter search method combines a set of diverse and high-quality candidate solutions by considering the weights and constraints of each solution.

Citation

Euchi, J. (2017), "Genetic scatter search algorithm to solve the one-commodity pickup and delivery vehicle routing problem", Journal of Modelling in Management, Vol. 12 No. 1, pp. 2-18. https://doi.org/10.1108/JM2-10-2015-0077