Cargando…

A capacitated multi pickup online food delivery problem with time windows: a branch-and-cut algorithm

Online food delivery companies, nowadays, allow a customer to place an order for a combination of dishes from one or more restaurants. To meet a customer’s demand, the company then arranges for the pickups from different restaurants, perhaps located distantly, before delivering them to the customer....

Descripción completa

Detalles Bibliográficos
Autores principales: Kohar, Amit, Jakhar, Suresh Kumar
Formato: Online Artículo Texto
Lenguaje:English
Publicado: Springer US 2021
Materias:
Acceso en línea:https://www.ncbi.nlm.nih.gov/pmc/articles/PMC8192046/
https://www.ncbi.nlm.nih.gov/pubmed/34131357
http://dx.doi.org/10.1007/s10479-021-04145-6
_version_ 1783705977017597952
author Kohar, Amit
Jakhar, Suresh Kumar
author_facet Kohar, Amit
Jakhar, Suresh Kumar
author_sort Kohar, Amit
collection PubMed
description Online food delivery companies, nowadays, allow a customer to place an order for a combination of dishes from one or more restaurants. To meet a customer’s demand, the company then arranges for the pickups from different restaurants, perhaps located distantly, before delivering them to the customer. The company caters to a set of such customers, through a fleet of capacitated vehicles. In this paper, we propose an augmented two-index formulation to find least cost vehicle routes to satisfy the set of customer requests under the constraints of time windows of the pickup and delivery locations along with the capacity constraints of the fleet of vehicles. We use branch-and-cut algorithm to solve the benchmark problem instances. The proposed formulation and the problem specific valid inequalities lead to more efficient solution performance as against the existing formulations. The computational experiments indicate that the proposed approach can solve a majority of benchmark problem instances with 25, 35 and 50 nodes, many of which were reported unsolved using exact solution approaches in the extant literature.
format Online
Article
Text
id pubmed-8192046
institution National Center for Biotechnology Information
language English
publishDate 2021
publisher Springer US
record_format MEDLINE/PubMed
spelling pubmed-81920462021-06-11 A capacitated multi pickup online food delivery problem with time windows: a branch-and-cut algorithm Kohar, Amit Jakhar, Suresh Kumar Ann Oper Res S.I. : Computational Logistics in Food and Drink Industry Online food delivery companies, nowadays, allow a customer to place an order for a combination of dishes from one or more restaurants. To meet a customer’s demand, the company then arranges for the pickups from different restaurants, perhaps located distantly, before delivering them to the customer. The company caters to a set of such customers, through a fleet of capacitated vehicles. In this paper, we propose an augmented two-index formulation to find least cost vehicle routes to satisfy the set of customer requests under the constraints of time windows of the pickup and delivery locations along with the capacity constraints of the fleet of vehicles. We use branch-and-cut algorithm to solve the benchmark problem instances. The proposed formulation and the problem specific valid inequalities lead to more efficient solution performance as against the existing formulations. The computational experiments indicate that the proposed approach can solve a majority of benchmark problem instances with 25, 35 and 50 nodes, many of which were reported unsolved using exact solution approaches in the extant literature. Springer US 2021-06-10 /pmc/articles/PMC8192046/ /pubmed/34131357 http://dx.doi.org/10.1007/s10479-021-04145-6 Text en © The Author(s), under exclusive licence to Springer Science+Business Media, LLC, part of Springer Nature 2021 This article is made available via the PMC Open Access Subset for unrestricted research re-use and secondary analysis in any form or by any means with acknowledgement of the original source. These permissions are granted for the duration of the World Health Organization (WHO) declaration of COVID-19 as a global pandemic.
spellingShingle S.I. : Computational Logistics in Food and Drink Industry
Kohar, Amit
Jakhar, Suresh Kumar
A capacitated multi pickup online food delivery problem with time windows: a branch-and-cut algorithm
title A capacitated multi pickup online food delivery problem with time windows: a branch-and-cut algorithm
title_full A capacitated multi pickup online food delivery problem with time windows: a branch-and-cut algorithm
title_fullStr A capacitated multi pickup online food delivery problem with time windows: a branch-and-cut algorithm
title_full_unstemmed A capacitated multi pickup online food delivery problem with time windows: a branch-and-cut algorithm
title_short A capacitated multi pickup online food delivery problem with time windows: a branch-and-cut algorithm
title_sort capacitated multi pickup online food delivery problem with time windows: a branch-and-cut algorithm
topic S.I. : Computational Logistics in Food and Drink Industry
url https://www.ncbi.nlm.nih.gov/pmc/articles/PMC8192046/
https://www.ncbi.nlm.nih.gov/pubmed/34131357
http://dx.doi.org/10.1007/s10479-021-04145-6
work_keys_str_mv AT koharamit acapacitatedmultipickuponlinefooddeliveryproblemwithtimewindowsabranchandcutalgorithm
AT jakharsureshkumar acapacitatedmultipickuponlinefooddeliveryproblemwithtimewindowsabranchandcutalgorithm
AT koharamit capacitatedmultipickuponlinefooddeliveryproblemwithtimewindowsabranchandcutalgorithm
AT jakharsureshkumar capacitatedmultipickuponlinefooddeliveryproblemwithtimewindowsabranchandcutalgorithm