Ravi's answers is dead on.
On Jul 8, 7:21 am, Ravishankar <[EMAIL PROTECTED]> wrote:
> On Sun, Jun 15, 2008 at 8:39 AM, howa <[EMAIL PROTECTED]> wrote:
>
> > Hi,
>
> > Consider a map, with N bus stations, and there are total L bus lines
> > operating on this set of stations
>
> > 1. Each line follow a particular path, it might not be symmetric (i.e.
> > the path from placeA=> placeB might be different from placeB to
> > placeA)
> > 2. Some statations are shared by several lines; but not all lines will
> > stop at a particular station
>
> > 3. Different lines has different cost even from the same origin and
> > destination, (i.e. Line 100. placeA => place B = $1USD, while for Line
> > 101, placeA => placeB =$1.5USD)
>
> > 4. Different lines of bus has different inter-arrival time (e.g. Line
> > 100 need to wait 10 minutes in average, Line 101 need to wait 6
> > minutes in average)
>
> > Now, you are requested to think of an algorithm, which get the
>
> > 1. Min. cost
> > 2. Min. traveling time (waiting time and running time)
> > 3. Min. the number of bus changes
>
> > What kind of algorithm should I explore if I want to solve the above
> > problem?
>
> (If exact solution is not possible, are there any simpler
>
> > implementations which should get some average-to-good result, e.g. GA
> > algorithm?)
>
> You need to use optimization techniques to find near to optimal solutions.
>
> My approach in solving the problem would be.
> 1. Define the lines for the bus both onward and return journey. You could
> maintain two lists one for onward and another return journey which contains
> the intermediate junctions of the route.
>
> 2. Each bus will have specific departure and arrival times at every
> junction. This is subject to change when it comes to a real implementation
> due to traffic jams, accidents (in general unavoidable circumstances). So
> the algorithm has to be an online algorithm whose further actions depend on
> the current data.
>
> 3. Next the optimizing criteria would be minimizing [travel time + waiting
> time] and/or minimizing the cost incurred for travel. It is easy to
> optimize one of the parameters. If we need to optimize on both parameters,
> then you are certain to wait longer if the cost for travel is less else the
> cost will be high for shorter wait time
>
> 4. Once you define the optimization function, try to find a line which gives
> optimum value.
>
> To determine the minimum number of change overs you need to have complete
> data of all the bus schedules, their current location, time to reach nodes,
> passenger preference and whatever parameters you define for the system. It
> is better to avoid vehicle change overs as it involves additional
> computation overhead.
>
> -Ravi
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---
