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 -~----------~----~----~----~------~----~------~--~---
