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

Amit Kohar () and Suresh Kumar Jakhar ()
Additional contact information
Amit Kohar: Indian Institute of Management Lucknow
Suresh Kumar Jakhar: Indian Institute of Management Lucknow

Annals of Operations Research, 2025, vol. 354, issue 2, No 7, 735-756

Abstract: Abstract 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.

Keywords: Food delivery; Multi pickup and delivery problem; Branch-and-cut; Vehicle routing problem (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10479-021-04145-6 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

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:spr:annopr:v:354:y:2025:i:2:d:10.1007_s10479-021-04145-6

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10479

DOI: 10.1007/s10479-021-04145-6

Access Statistics for this article

Annals of Operations Research is currently edited by Endre Boros

More articles in Annals of Operations Research from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().