Abstract / Excerpt:

The Hungarian method is a time tested algorithm for solving assignment problems. It has a polynomial complexity, specifically, O(n3).

This study applied the Hungarian algorithm to the taxi assignment problem in a simulation. It incorporated real world variables like differing speeds on road segments, random road side passenger pickups and road closures.

The simulation engine consisted of a directed weighted graph that represented the road network, a predetermined number of taxi units available, a predetermined random roadside passenger pickup chance, a predetermined range n to m where n and m are the minimum and maximum numbers of passenger randomly inserted per a predetermined time window size.

The study also featured some customized improvements to the original Hungarian algorithm that improved the run time performance of the algorithm. The improvements became more apparent as the search space grew bigger when the number of taxis and/or the number of passengers were increased.

A notable achievement of the study was the ability of the algorithm to determine assignment in around 2 seconds given a search space with a size of 22,500 possibilities.

Info

Source Institution	Ateneo de Davao University
Unit	Computer Studies
Authors	Mar Vince Emmanuel Co Reyes, Hyangelo Henry Hao
Page Count	10
Place of Publication	Davao City
Original Publication Date	March 1, 2008
Tags	Algorithm, Computer Studies, Hungarian, Taxi Assignment Problem

Preview