Advanced Traveler Information System: Itinerary Optimization as an Orienteering Problem Using Iterative Local Search-Hill Climbing Algorithm

Traffic congestion is a problem that becomes government concern in many big cities like Surabaya. Some initiatives have been carried out by the government to decrease the intensity of traffic congestion, ranging from various policy like special lane for motorcycle, odd - even license plate, etc. However, it is yet to be successful to decrease the heavy traffic in many big cities in Indonesia. The right solution tends to encourage people to use public transport instead of private cars. Within the framework of Intelligent Transport System, this paper proposes an advanced traveller information system with itinerary optimisation by Angkot, a common public transport mode in Indonesia. The itinerary optimisation is modelled as an orienteering problem and is solved using iterative local search - hill climbing algorithm. The experiment results show that generally the proposed algorithm could solve the problem fast and effectively. In addition to propose the initial algorithm, the main contribution of this paper is a new dataset for orienteering problem that may encourage researcher to come up with more sophisticated algorithm. Eventually, the proposed system could encourage more people to use public transport.