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....
Autores principales: | , |
---|---|
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 |