A branch-and-cut method for the Vehicle Relocation Problem in the One-Way Car-Sharing
Abstract: The purpose of this thesis is to develop an algorithm which solves the Vehicle Relocation Problem in the One-Way Car-Sharing (VRLPOWCS) as fast as possible. The problem describes the task of relocating the cars to areas with the largest demand. The chauffeurs who relocate the cars are transported by shuttle buses. Each car is assigned an individual relocation utility. The objective is to find shuttle tours that maximise in a given time the relocation utility while balancing the distribution of the cars. The VRLPOWCS is formulated as a mixed integer linear program. Since this problem is NP-complete we choose the branch-and-cut method to solve it. Using additional cutting planes – which exploit the structure of the VRLPOWCS – we enhance this method. Tests on real data show that this extended algorithm can solve the VRLPOWCS faster.
AT THIS PAGE YOU CAN DOWNLOAD THE WHOLE ESSAY. (follow the link to the next page)