Solution space analysis for the bike request scheduling problem

Nicholas Vergeylen, Kenneth Sörensen and Daniel Palhazi Cuervo

Working Papers from University of Antwerp, Faculty of Business and Economics

Abstract: The Bike Request Scheduling Problem (BRSP) is a recently introduced combinatorial optimization problem the aim of which is to assign a number of predefined bicycle pick-or-drop instructions, called requests, to a set of vehicles and determine the sequence (routes) in which the vehicles should perform the requests. A natural and elementary operation in heuristics for the BRSP is request insertion (RI), the operation of inserting a request in a specific position in a route. Solutions of the BRSP are connected in the solution space through RI operations. This results in a distance between solutions called the RI distance. A better understanding of the solution space and the RI operator is necessary to improve both problem understanding and solution methods using RI. Therefore, we first perform a solution space cardinality analysis. Secondly, we formulate properties of the RI-metric and, finally, we visualize the solution space. We demonstrate that the original BRSP model formulation yields a very large solution space, a problem that we solve by introducing symmetrybreaking constraints. Furthermore, we propose an expression for the cardinality of the solution space, and derive lower bounds which show that enumeration is intractable and random search is generally ineffective. Finally, we visualize the solution space of the BRSP using the RI distance, which can help understand the effects of other, more complex operators and of introducing algorithm components such as evaluation functions. A few alternatives of evaluation functions are developed and analyzed.

Keywords: Combinatorial optimization; Combinatorial complexity; Bike request scheduling problem; Bicycle repositioning; Multi dimensional scaling (search for similar items in EconPapers)
Pages: 30 pages
Date: 2018-02
New Economics Papers: this item is included in nep-tre
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://repository.uantwerpen.be/docman/irua/eda2ca/149166.pdf (application/pdf)

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:ant:wpaper:2018005

Access Statistics for this paper

More papers in Working Papers from University of Antwerp, Faculty of Business and Economics Contact information at EDIRC.
Bibliographic data for series maintained by Joeri Nys ().