Facial reconstruction

Search LJMU Research Online

Browse Repository | Browse E-Theses

The Offline Group Seat Reservation Knapsack Problem with Profit on Seats

Deplano, I, Yazdani, D and Nguyen, TT (2019) The Offline Group Seat Reservation Knapsack Problem with Profit on Seats. IEEE Access, 7. pp. 152358-152367. ISSN 2169-3536

The Offline Group Seat Reservation Knapsack Problem With Profit on Seats.pdf - Published Version
Available under License Creative Commons Attribution.

Download (5MB) | Preview
Open Access URL: https://doi.org/10.1109/ACCESS.2019.2948322 (Published version)


In this paper we present the Group Seat Reservation Knapsack Problem with Profit on Seat. This is an extension of the the Offline Group Seat Reservation Knapsack Problem. In this extension we introduce a profit evaluation dependant on not only the space occupied, but also on the individual profit brought by each reserved seat. An application of the new features introduced in the proposed extension is to influence the distribution of passengers, such as assigning seats near the carriage centre for long journeys, and close to the door for short journeys. Such distribution helps to reduce the excess of dwelling time on platform. We introduce a new GRASP based algorithm that solves the original problem and the newly proposed one. In the experimental section we show that such algorithm can be useful to provide a good feasible solution very rapidly, a desirable condition in many real world systems. Another application could be to use the algorithm solution as a startup for a successive branch and bound procedure when optimality is desired. We also add a new class of problem with five test instances that represent some challenging real-world scenarios that have not been considered before. Finally, we evaluate both the existing model, the newly proposed model, and analyse the pros and cons of the proposed algorithm.

Item Type: Article
Subjects: H Social Sciences > HE Transportation and Communications
T Technology > T Technology (General)
Divisions: Maritime & Mechanical Engineering (merged with Engineering 10 Aug 20)
Publisher: Institute of Electrical and Electronics Engineers (IEEE)
Date Deposited: 14 Oct 2019 08:39
Last Modified: 05 Aug 2022 11:00
DOI or ID number: 10.1109/ACCESS.2019.2948322
URI: https://researchonline.ljmu.ac.uk/id/eprint/11561
View Item View Item