Comparison of Genetic Operators for the Multiobjective Pickup and Delivery Problem

Connor Little (), Salimur Choudhury, Ting Hu and Kai Salomaa
Additional contact information
Connor Little: School of Computing, Queen’s University, Kingston, ON K7L 3N6, Canada
Salimur Choudhury: School of Computing, Queen’s University, Kingston, ON K7L 3N6, Canada
Ting Hu: School of Computing, Queen’s University, Kingston, ON K7L 3N6, Canada
Kai Salomaa: School of Computing, Queen’s University, Kingston, ON K7L 3N6, Canada

Mathematics, 2022, vol. 10, issue 22, 1-21

Abstract: The pickup and delivery problem is a pertinent problem in our interconnected world. Being able to move goods and people efficiently can lead to decreases in costs, emissions, and time. In this work, we create a genetic algorithm to solve the multiobjective capacitated pickup and delivery problem, adapting commonly used benchmarks. The objective is to minimize total distance travelled and the number of vehicles utilized. Based on NSGA-II, we explore how different inter-route and intraroute mutations affect the final solution. We introduce 6 inter-route operations and 16 intraroute operations and calculate the hypervolume measured to directly compare their impact. We also introduce two different crossover operators that are specialized for this problem. Our methodology was able to find optimal results in 23% of the instances in the first benchmark and in most other instances, it was able to generate a Pareto front within at most one vehicle and +20% of the best-known distance. With multiple solutions, it allows users to choose the routes that best suit their needs.

Keywords: optimization; vehicle routing; genetic algorithm; local search; pickup and delivery (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
https://www.mdpi.com/2227-7390/10/22/4308/pdf (application/pdf)
https://www.mdpi.com/2227-7390/10/22/4308/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:10:y:2022:i:22:p:4308-:d:975479

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().