SEAT ASSIGNMENT ALGORITHM FOR RECEIVING PASSENGERS CLOSE TO OPTIMAL NUMBER OF PASSENGERS IN TWO OR MORE APPOINTED CONNECTED CARS OF TRAIN

摘要

Disclosed is a seat assignment algorithm for receiving passengers close to the optimal number of passengers in a train. According to the present invention, a passenger is assigned to a car of a train, not a seat, with respect to two or more appointed cars connected in a train, so as to freely seat an empty seat in the appointed cars, or a seat is appointed to minimize seat moving in the appointed cars so that moving between the cares is allowed once between neighboring cares when moving between the cares is required. Thus, the present invention provides a ticket issuance method to receive the same number of passengers as the number of passengers received in an optimization method when there is no ticket cancelation according to an optimal offline algorithm. When there is ticket cancelation, the present invention ensures reception of two thirds of the number of passengers, who want a ticket after someone else′s ticket cancelation, according to the optimal offline algorithm. For example, when a seat assignment algorithm of the present invention is used, if 30% of tickets are canceled and the same number of passengers capable of being received in the optimization method as the number of passengers having canceled the ticket want tickets, the algorithm receives 90% or more of the total passengers capable of being received in the optimization method.;COPYRIGHT KIPO 2016