The interval min–max regret knapsack packing-delivery problem

Shijin Wang, Wenli Cui, Feng Chu and Jianbo Yu

International Journal of Production Research, 2021, vol. 59, issue 18, 5661-5677

Abstract: This paper studies an interval data min–max regret (IDMR) version of the packing-delivery problem, in which a 0-1 knapsack problem is for parcel packing and a capacitated travelling salesman problem is for parcel delivery. The parcel profits for the courier and the tour costs are uncertain and they can take any value from a specific interval with lower and upper bound values. The problem is how to select and deliver a subset of parcels to minimise the maximum regret of net profit which is the difference between the total profits of the selected parcels and the total delivery costs, to deal with the trade-off of the solution robustness and performance. To tackle the problem effectively, we first prove the worst-case scenario of a solution to the problem, based on which, a mixed integer linear programming is formulated. A Benders-like decomposition algorithm is then developed to solve small-scale problems to optimality within the manageable computation time. For medium- and large-scale problems, a simulated-annealing-based heuristic method with a local search procedure is designed. Extensive computational experiments show the efficiency and effectiveness of the proposed methods.

Date: 2021
References: Add references at CitEc
Citations:

Downloads: (external link)
http://hdl.handle.net/10.1080/00207543.2020.1789235 (text/html)
Access to full text is restricted to subscribers.

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:taf:tprsxx:v:59:y:2021:i:18:p:5661-5677

Ordering information: This journal article can be ordered from
http://www.tandfonline.com/pricing/journal/TPRS20

DOI: 10.1080/00207543.2020.1789235

Access Statistics for this article

International Journal of Production Research is currently edited by Professor A. Dolgui

More articles in International Journal of Production Research from Taylor & Francis Journals
Bibliographic data for series maintained by Chris Longhurst ().