Location-Based Taxi Service in Wireless Communication Environment

by Aloizio Pereira da Silva

Advisor: Geraldo Robson Mateus

Dissertation presented to the Graduate Program in Computer Science at
the Federal University of Minas Gerais, in partial fulfillment of the
requirements for the degree of Master of Computer Science.

Belo Horizonte
March 25, 2002

Abstract

The convergence of three technologies, the Internet, wireless and location
technologies is creating new opportunities for mobile devices. Mobile
location-based services are emerging as one of the study topics in the
mobile communication area. Basically, they use both the information
of mobile unit's (MU) physical position, which can be obtained by GPS
(Global Positioning System) and the information contained in a user
profile to answer to his needs at that moment. Many investments have been
made in the field of networks in resource allocation, mainly in wireless
communication networks. Recently, wireless communication has moved from
voice service to data services. Wireless protocol makes it possible
for commonly used devices such as cell phones, PCs and PDAs (Personal
Digital Assistants) to access and to manage information anywhere and
anytime. In addition, there are a lot of other objects, that make part
of a particular set. For instance, cars (taxis, ambulances, police car,
trucks) aeroplane, etc. Due to that, it becomes necessary the knowledge
where they are physically located and most of them will not be static,
but constantly moving. This shift to the mobile world presents new aspects
to the problem of resource allocation.

The aim of this work is to model an application of mobile location-based
service taking into account the available infrastructure of a wireless
communication network. The process under study is developing a more
efficient strategy for transporting users of taxi service from one
location to another. The strategy explored in practice tends to be
either centralized as in the case of dispatchers or static as in the
case of courier service trucks that have pre-assigned pick-ups and
deliveries in certain geographic regions. The implemented prototype uses
a new strategy to allocate a specific taxi to one MU. In this case the
assignment algorithm is similar, to those used in problems studied in
the area of network optimization. The proposed strategy here is based
on the MU communication with the taxi via a server, which performs
whole assignment processing using location data. This prototype allows,
through simulation, to compare the currently used queue-type strategy
with the new solution proposal. Numerical results show the benefits of
allocation procedure to assign taxis to MUs and to optimize the distance
traveled and travel time if applied in a real-time context.