Solution space analysis for the bike request scheduling problem

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.