Adaptive large neighborhood search for the pickup and delivery problem with time windows, profits, and reserved requests

Yuan Li, Haoxun Chen and Christian Prins

European Journal of Operational Research, 2016, vol. 252, issue 1, 27-38

Abstract: This paper addresses the Pickup and Delivery Problem with Time Windows, Profits, and Reserved Requests (PDPTWPR), a new vehicle routing problem appeared in carrier collaboration realized through Combinatorial Auction (CA). In carrier collaboration, several carriers form an alliance and exchange some of their transportation requests. Each carrier has reserved requests, which will be served by itself, whereas its other requests called selective requests may be served by the other carriers. Each request is a pickup and delivery request associated with an origin, a destination, a quantity, two time windows, and a price for serving the request paid by its corresponding shipper. For each carrier in CA, it has to determine which selective requests to serve, in addition to its reserved requests, and builds feasible routes to maximize its total profit. A Mixed-Integer Linear Programming (MILP) model is formulated for the problem and an adaptive large neighborhood search (ALNS) approach is developed. The ALNS involves ad-hoc destroy/repair operators and a local search procedure. It runs in successive segments which change the behavior of operators and compute their own statistics to adapt selection probabilities of operators. The MILP model and the ALNS approach are evaluated on 54 randomly generated instances with 10–100 requests. The computational results indicate that the ALNS significantly outperforms the solver, not only in terms of solution quality but also in terms of CPU time.

Keywords: Vehicle routing problem; Pickup and delivery problem; Time window; Profit; Adaptive large neighborhood search (search for similar items in EconPapers)
Date: 2016
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (37)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221715011716
Full text for ScienceDirect subscribers only

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:eee:ejores:v:252:y:2016:i:1:p:27-38

DOI: 10.1016/j.ejor.2015.12.032

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().