Abstract:
The present invention may enable the efficient allocation of a plurality of vehicles ( 300 ) to a plurality of passengers ( 100 ) traveling between independent origins and destinations. In one or more embodiments, the method may collect the locations of vehicles( 300 ), and the origins and destinations of traveling parties( 100 ). The method may generate a set of routes that it deems superior to other known sets of routes, making use of an electronic map( 202 ), which will provide street lengths, estimated travel times, and estimated costs along streets. Each route may include a carrying vehicle equipped with a console( 300 ), and that carrying vehicle&#39;s console( 300 ) may be wirelessly sent information identifying the origins and destinations of the parties( 100 ) which that carrying vehicle is to transport, thus dispatching the vehicle. 
     The method may use one of several metrics to determine length or cost along a route, and it may use them alone or in combination. For example, the “length” of a route from point (A) to point (B) may be the estimated time to travel from point (A) to point (B), or the distance along that route in kilometers, or the amount of money costs accrued by a vehicle( 300 ) or person( 100 ) traveling along that route. The metrics may be used in combination, for example. if a particular route is estimated to take 45 minutes to traverse, and requires payment of a $5 toll, the method may value time at $10 per hour, and add 30 minutes to the time of travel for that segment of that route. 
     In each embodiment, the method may use one of several possible criteria to select route sets. For example, in some embodiments, the best route set may be the route set with the estimated lowest total travel time for all passengers ( 100 ) on all routes in the set; whereas in other embodiments, the criteria may additionally include travel time for vehicles. For example, other embodiments may seek to minimize linear distance along routes. As a further example, still more embodiments may use one of several measures of efficiency, such measures to be described herein.

Description:
SUMMARY 
       [0001]    Providers of surface transportation are faced with the problem of carrying independent passengers from separate origins to separate destinations using a limited number of vehicles. Such providers wish to deliver their passengers within the shortest possible time, and to minimize the time, distance, or cost accrued by the vehicles and by the passengers they serve. 
         [0002]    Most schemes for delivery of passengers involve either fixed, prearranged routes, or the on-demand service of single passengers. In the case of fixed routes (typically served by buses, but also including trains, airplanes, or other vehicles), a passenger must find a carrier that is traveling to the general area of his destination, and he must arrange to embark at a prearranged time and fixed place. The carrier must also commit resources (vehicles and operators) to routes without knowing in advance if any passengers need to be served, or if the vehicles employed are sufficient to carry the number of passengers desiring travel. Vehicles on fixed routes do have the advantage of carrying multiple unrelated passengers at a time, harvesting lower costs per passenger: however, the passenger&#39;s overall journey is usually completed slowly because the passengers&#39; travel plans must be matched with the fixed routes and schedules of the provider. 
         [0003]    On the other hand, on-demand transportation (notably taxicabs) is available more quickly, but providers are less able to carry passengers with different origins or destinations in the same vehicle at the same time. Moreover, such providers usually lack an efficient method for allocating vehicles to passengers in such a way that minimizes both passenger travel time and the time the vehicles must travel to serve them, which increases the cost of the service significantly, and the time it takes for the passengers to receive service. While it would behoove such providers to reduce costs by carrying passengers with different origins and/or destinations in the same car—essentially, sharing a car—they struggle to do so while at the same time delivering prompt service to all of their passengers. In particular, they find it difficult to allocate the vehicles available among the persons desiring service. Even if the carriers are able to allocate passengers among vehicles in advance, any new passengers requesting service while the vehicles are already enroute may not receive service until after the vehicles serve all the current passengers; and new vehicles coming into service when existing vehicles are already serving passengers might not be deployed promptly. Moreover, passengers on a vehicle suffering a breakdown, or designated to be served by a vehicle which breaks down (or is otherwise rendered unavailable) before meeting them are left without effective service by carriers operating using existing methods. 
       BACKGROUND 
       [0004]    Numerous attempts have been made to streamline transportation by better matching travelers with vehicles. One such attempt is described in DE102010003610 A1 (Barnickel, et. al., hereafter “Barnickel”). Barnickel&#39;s approach is to permit a driver to designate a range of times or distances within which s/he is willing to detour to pick up an additional passenger. Passengers specify either a time to be picked up or dropped off, or range of “tolerances” (describing ranges either of time or of place) within which they would be willing to accept a ride from a carpool provider. This approach suffers a disadvantage in that the passenger is not guaranteed a ride if the tolerances do not match: if the only car available cannot make the pickup within the passenger&#39;s range of tolerances, the passenger is denied service. Barnickel&#39;s approach does not seek to optimize either passenger travel time or the car&#39;s driving time; rather, it either permits or denies rides on the basis of meeting certain fixed criteria. If several rides fit Barnickel&#39;s criteria, Barnickel&#39;s approach will not choose the best match among them, but will merely make one or more minimally acceptable matches. If a new car becomes available after a passenger has been matched with a car, Barnickel&#39;s method will not allocate that car to that passenger, even if doing so would provide superior service. 
         [0005]    Patent U.S. Pat. No. 5,214,689 A (O&#39;Sullivan) describes a method of matching passengers with vehicles, but requires that the vehicles transit a fixed station, and that passengers either embark or disembark there. 
         [0006]    Patent U.S. Pat. No. 6,751,548 B2 (Boulard and Fox) describes a ride matching scheme that makes use of straight-line distance between points. This is not the same as using time as calculated by speed limits or other road information. In cases where actual distance traveled varies from straight-line distance (such as in rides spanning both sides of a river, with the nearest bridge at some distance), this method will suffer inaccuracy and fail to deliver optimal efficiency. 
         [0007]    Patent U.S. Pat. No. 7,080,019 B1 (Hurzeler) describes a method by which people traveling may locate other people traveling in the same area. It does not permit rerouting of vehicles already in motion, and does not guarantee that an acceptable match will be made even if vehicles are active. 
         [0008]    Likewise Patent U.S. Pat. No. 4,360,875 A (Behnke) can similarly leave a passenger standing if an acceptable match cannot be found. This can occur even if a car is available to take passengers. Moreover. Behnke&#39;s method requires that the geographic area to be served is partitioned into a grid, and the grid squares are used to inform the matching process. This procedure is prone to inefficiency and error because cities and landscapes are not well modeled by rectangular grids. 
         [0009]    Patent U.S. Pat. No. 5,272,638 A (Lineberry. et. al.) proposes a method for optimizing travel along a route containing a series of waypoints (“destinations”), but does not support the notion of a passenger or other load (e.g. cargo) that must be picked up at one location and dropped off at another, and is thus inapplicable to a situation in which persons or goods are transported from Point A to Point B. with Point B necessarily coming later than Point A. 
         [0010]    The invention of Patent U.S. Pat. No. 5,604,676 A (Penzias) reports a plurality of paths and prices to the passenger, who must pick one, entailing a certain complexity and delay. 
         [0011]    Patent U.S. Pat. No. 8,438,118 B2 (Ho) covers a method to improve transportation of “items or packages” by seeking a more efficient route, and by consolidating shipments. Ho&#39;s method requires “time attributes” to function, these being windows or ranges of time within which a package can be picked up or delivered, similar to Barnickel&#39;s “tolerances”, and undesirable for the same reasons. At no point does Ho describe his system as being suitable for moving people rather than objects. 
         [0012]    The academic literature contains a paper on efficient vehicle routing (Algorithms for Capacitated Vehicle Routing, Charikar et. al., SIAM J. Computing, Vol. 31, No. 3, pp. 685-682, hereafter “Charikar”). Charikar describes mathematical methods for minimizing the distance traveled by a vehicle delivering “pegs” from origins to destinations. Charikar&#39;s algorithms all are focused on reducing distance traveled by the delivery vehicle, but do not minimize either time or distance for the cargo (“pegs”). Charikar&#39;s methods all assume the vehicles will begin and end their journeys at the same place, which places this optimization problem into a category well recognized by persons skilled in the art of computer science as “NP-complete”. Such problems are for all practical purposes mathematically impossible to solve for any but a small number of vehicles and pegs, which means Charikar&#39;s methods are impractical for any but a very small number of pegs. 
       Advantages 
       [0013]    Certain aspects of the present invention are directed towards the allocation of vehicles among passengers such that the total time the passengers spend traveling, or the distance they cover, is minimized. 
         [0014]    Certain aspects of the present invention may result in a reduced time or distance the vehicles must travel to serve them and/or costs accrued by the service. 
         [0015]    Certain aspects of the present invention may cause passengers presenting rides that are easiest to efficiently serve to be served soonest, encouraging such passengers to continue patronizing the service. 
         [0016]    Certain aspects of the present invention may cause passengers presenting rides that are approximately equally efficiently served, to be served with approximately equal dispatch. 
         [0017]    Certain aspects of the present invention may permit the service providers to guarantee passengers that a ride ordered will result in a vehicle dispatched, provided an active vehicle is present with enough seats to accommodate all persons traveling together as part of that ride. 
         [0018]    Certain aspects of the present invention may permit the service providers to schedule new rides at any point, dynamically re-allocating resources and re-routing vehicles in response to new ride requests, cancellations of existing rider requests, or “no-show” passengers. 
         [0019]    Certain aspects of the present invention may permit the service providers to dynamically re-allocate resources and re-route vehicles in response to the unexpected addition or loss of a vehicle, such as that caused by a new vehicle coming available, or a working vehicle opting to go off duty. 
         [0020]    Certain aspects of the present invention may permit a vehicle becoming available to immediately begin serving customers who had booked rides prior to that vehicle becoming available. 
         [0021]    Certain aspects of the present invention may permit recovery from a situation arising when a vehicle bearing passengers is unable to complete its ride due to mechanical failure or other disability. 
         [0022]    Certain aspects of the present invention may permit the provision of either a faster (premium) or slower (discount) service to different passengers. 
         [0023]    Certain aspects of the present invention may permit the provision of a service that minimizes the time spent on one part of a passenger&#39;s journey, for example, the time spent waiting for a pickup. 
         [0024]    Certain aspects of the present invention may permit the selection of an optimally efficient set of routes using combinations of money cost of a route, distance traveled a route, or time to travel along a route, or a set of routes. 
         [0025]    Certain aspects of the present invention permit the selection of an efficient set of routes without requiring any routes to return to their starting point, thus avoiding intractable computational complexity when selecting routes. 
       Descriptions 
       [0026]    In the following descriptions, certain specific details are provided to give an understanding of the invention. One skilled in the art will recognize that the invention may be practiced without one or more of the specific details, or with other methods, materials or components, etc. In other cases, well known components or operations are not described in the interest of clarity of exposition. 
         [0027]    When reference is made to “an embodiment” or “one or more embodiments”, it means that a particular structure, feature or method is included in at least one embodiment of the present invention. It does not necessarily mean the structure or feature or method is included in all embodiments. The particular structures, features, or methods here described may be combined in one or more embodiments. In particular, any description that makes use of a vehicle, passenger or hub may be understood to apply to any number of such vehicles or passengers or hubs. 
         [0028]    In any case where either a masculine or feminine article of speech is used (he, she, him, her, his, hers, etc.), it is intended that the person(s) so referenced can be either male or female, without regard to the gender used to refer to him/her. 
     
    
     
       DETAILED DESCRIPTION 
       Drawings 
       Figures and Tables 
         [0029]    FIG. A is a schematic diagram of a system suitable for implementing various aspects or embodiments of the present invention. It depicts: 
           [0030]    [A] A party of travelers  100 , numbering one or more persons, who know where they are and where they wish to go, and who have way to communicate  102  the origin and desired destination, and optionally the number of persons in the party, to a dispatch unit  200 , and 
           [0031]    [B] A dispatch unit  200 , containing:
       A communications link  102  to parties of travelers  100 , suitable for communication of origins and destinations of desired rides, and possibly numbers of persons in the party, and   A non-transitory computer-readable storage device storing instructions for controlling a computing environment to perform a method  201  in a computing system for generating routes for transportation of parties of travelers  100  with known origins and destinations, and   An electronic map  202  on computer-readable data storage media, containing information describing roads, highways, streets, and intersections, and of finding shorter or shortest, faster or fastest, and cheaper or cheapest routes between points in the map, and making the routes or information available to the routing method  201 , and   A data storage unit  203 , such as a computer hard disk or other computerized storage media, or a connection to a computer with such media, and the data storage unit  203  being available to the routing method  201 , and   A wireless communication interface  204  with vehicle consoles (to be described in [C]), and       
 
           [0037]    [C] A vehicle and driver, comprising:
       A vehicle console  300 , comprising a computer, smart phone, tablet computer, or other computing device, and an interface to the vehicle operator, through which the operator may enter or receive information, and   A locating device  301 , such as a Global Positioning System (GPS) unit, with a data interface to the vehicle console  300 , and   A data storage unit  302 , with a data interface to the vehicle console  300 , and   A wireless communications interface  204  with one or more dispatch units  200 .       
 
           [0042]    FIG.  0 /Table 0 describe a route involving one car and one passenger, and serve principally to illustrate the notation used in  FIGS. 1-20  and Tables 1-20. 
           [0043]    FIGS.  1  &amp;  2 /Tables 1 &amp; 2 describe the optimization of a route involving a single car and two passengers. 
           [0044]    FIGS.  3  &amp;  4 /Tables 3 &amp; 4 describe the optimization of a route involving two cars and a single passenger. 
           [0045]    FIGS.  5  &amp;  6 /Tables 5 &amp; 6 describe the optimization of a route involving two cars and two passengers. 
           [0046]    FIGS.  7  &amp;  8 /Tables 7 &amp; 8 describe the optimization of a route involving two cars and two passengers, in which one of the passengers is given premium service. 
           [0047]    FIGS.  9  &amp;  10 /Tables 9 &amp; 10 describe the optimization of a route involving two cars and two parties of travelers, in which one party of travelers comprises two persons, and the other party of travelers comprises one person. 
           [0048]    FIGS.  11  &amp;  12 /Tables 11 &amp; 12 describe the optimization of a route involving one car and two passengers, with one of the passengers requesting a ride that is not possible to serve as efficiently as that of the other passenger. 
           [0049]      FIGS. 13. 14  &amp;  15 /Tables 13. 14. &amp; 15 describe the optimization of a route involving two cars and two travelers, with one of the cars becoming available only after a passenger has already embarked upon the first car. 
           [0050]      FIGS. 16. 17  &amp;  18 /Tables 16. 17. &amp; 18 describe the optimization of a route involving one car and two passengers, in which one of the passengers does not book service until after the other passenger has embarked upon the car. 
           [0051]    FIGS.  19  &amp;  20 /Tables 19 &amp; 20 describe the optimization of a route involving two cars and two passengers, in which a hub is utilized. 
       
    
    
     DRAWINGS  
     Reference Numerals 
       [0000]    
       
           100 —passenger, or party of travelers, with wireless communications device 
           102 —wireless communications interface between passenger and dispatch unit 
           200 —dispatch unit 
           201 —routing method 
           202 —electronic map 
           203 —data storage unit 
           204 —wireless communications interface between vehicle console and dispatch unit 
           300 —vehicle console 
           301 —positioning system 
       
     
         [0061]      0302 —data storage unit 
       DETAILED EMBODIMENTS 
       [0062]    Definitions 
         [0063]    In one or more embodiments, a passenger  100  may be a member of a party of travelers  100 , which may include any number of passengers  100  greater than zero, and a “party of travelers”  100  may include one or more than one passengers  100 , and the terms “passenger”  100  and “party of travelers”  100  may be used interchangeably. 
         [0064]    In one or more embodiments, “enroute” shall mean for any given passenger  100  any point in time or space at which that passenger  100  has yet to arrive at his destination, and for any given vehicle “enroute” shall mean any point in time or space at which the vehicle has not yet completed serving all passengers  100  it is dispatched to serve. 
         [0065]    In one or more embodiments, a “vehicle console”  300  may mean a computer, smart phone, tablet computer, or other computing device, the device being equipped with an interface by which an operator of the vehicle may enter or receive information, and also equipped with a wireless communication interface  204 , and possibly also equipped with a locating device  301 , such as a global positioning system (GPS), and possibly also equipped with a data storage unit  302 , such as a computer hard disk or FLASH memory. 
         [0066]    In one or more embodiments, a “vehicle” or “car” may be understood to mean a wheeled motor vehicle and driver, equipped with a vehicle console  300 . In some embodiments, “vehicle” and “vehicle console” may be used interchangeably, but in all such cases it is assumed that the console in the instant case is borne upon the vehicle in the instant case. 
         [0067]    In one or more embodiments, a “driver” of a vehicle may mean either a person driving a vehicle as such is usually understood, or a machine capable of guiding and controlling a vehicle. 
         [0068]    In all embodiments, “booking” a ride is understood to mean the process of a passenger  100  notifying a service with a dispatch unit  200  that the passenger  100  desires transportation from a given origin to a given destination, perhaps for a given number of persons, and of the service recording the particulars of that request. A “ride” is defined as the combination of origin and destination of the traveling party  100 , and possibly also the number of passengers  100  in the traveling party  100 . 
         [0069]    In one or more embodiments, “dispatching” a ride may mean the process of a service with a dispatch unit  200  notifying a given vehicle  300  by way of the vehicle console  300  that that vehicle  300  is required to serve a certain ride, and of either the vehicle&#39;s console  300  or the dispatch unit  200 , or possibly both the vehicle console  300  and the dispatch unit  200  recording the particulars of the ride: and the dispatch unit  200  possibly recording the identity of the vehicle  300  serving that ride. 
         [0070]    In one or more embodiments, “embarking” a passenger  100  may mean the passenger physically boarding the vehicle  300 , and the vehicle  300  notifying the dispatch unit  200  that the embarkation has occurred, and the dispatch unit  200  recording the facts of the embarkation. Likewise, “disembarking” a passenger  100  may mean the passenger  100  physically leaving the vehicle  300 , and the vehicle  300  notifying the dispatch unit  200  that this has occurred, and the dispatch unit  200  recording the facts of the disembarkation. The phrase “picked up” shall be synonymous with “embarked”, and the phrase “dropped off” shall be synonymous with “disembarked”. 
         [0071]    In one or more embodiments, a “travel metric” means a measure of time, distance, or money, and “travel cost” is the sum of one or more travel metrics along a route, possibly but not necessarily including money. 
         [0072]    Each travel metric is expressed in one “unit of measure”, which is defined to be a unit of distance (for example, kilometers) or of time (for example, minutes) or of money (for example, dollars). 
         [0073]    “Passenger travel cost” for a given passenger  100  is the sum of one or more travel metrics accrued before that passenger  100  arrives at his destination. 
         [0074]    “Vehicle travel cost” is the sum of one or more travel metrics accrued by a vehicle  300  between a given point and a subsequent point at which a passenger or passengers  100  are embarked or disembarked. 
         [0075]    In one or more embodiments, we may choose to define a “hub” as a point on earth with known location, which has facilities for vehicles  300  to enter, leave, embark, and disembark passengers  100 , and which is an appropriate place for passengers  100  to await a vehicle  300  to transport them. 
         [0076]    In one or more embodiments, we may choose to describe a route as a “feasible route”. For any feasible route for a given party of travelers  100 , all of the following are true, except when otherwise specified herein:
       (1) The party  100  is to be embarked at its origin:   (2) The party  100  is to be disembarked at its destination;   (3) Disembarkation of a given party  100  occurs after embarkation of the given party  100 : and   (4) At least one of the following is true for any given party  100 :
           (a) The party  100  is to be disembarked from the same car  300  that embarks it, or   (b) The party  100  is to be disembarked at a hub, and subsequently embarked upon another vehicle  300 , the vehicle  300  traveling on a feasible route.   
               
 
         [0083]    An “infeasible route” shall be defined as a route which violates one or more of these rules, except when otherwise specified herein. 
         [0084]    In one or more embodiments. “route” may be used interchangeably with “feasible route”, except where specifically noted. In particular, a “route set” or “set of routes” shall mean a set of one feasible route, or more than one feasible routes. 
         [0085]    In one or more embodiments, routes may be described as “better” or “best”, which means “having the lesser total travel metric” or “having the least total travel metric” compared to other routes. For example, if the relevant travel metric is time, the “best” route is that which can be completed in the least time; if the relevant metric is distance, the “best” route is the shortest: and if money costs are being used. “best” means cheapest. 
         [0086]    Routes will be diagrammed by labeling the pickup point with an uppercase letter (e.g. ‘A’) and the drop-off with the same letter in lower case (e.g. ‘a’). 
         [0087]    Cars  300  will be labeled with an uppercase ‘X’ followed by a number, e.g. ‘X 1 ’. 
         [0088]    Routes may be described by connecting cars  300  to pickup and drop-off points by arrows (‘-&gt;’) in order, for example, a ride in which car X 1  picks up passenger(s)  100  at point (A) and drops them off at point (a) can be written as X 1 -&gt;A-&gt;a. 
         [0089]    A party  100  being picked up at point (A) may be referred to as passenger(s) (A) or party (A), and so on for (B), (C), etc. When it is necessary to designate a party (A) disembarking at a hub, this may be rendered (particularly in tables) as (A−). when party (A) embarks at a hub, it may be rendered as (A+). This notation may of course be extended to parties (B), (C), (D), etc. 
         [0090]    In one or more embodiments, we may find it useful to define a “solo” route as being the best feasible route that a party  100  can travel, assuming that no other parties  100  are traveling. For example, if parties  100  (A), (B), and (C) need rides at the same time, and cars ( 300 ) X 1  and X 2  are active, and the metric employed is time, the solo route for party (A) is simply the feasible route that will carry party (A) to its destination in the shortest time, without regard to the other parties. Likewise, parties  100  (B) and (C) also have solo routes, which may or may not be compatible with party (A)&#39;s solo route (they may use the same car  300 , for instance). 
         [0091]    In one or more embodiments, a “direct route” may be the best path between a given passenger&#39;s origin and destination. A direct route lacks a carrying vehicle and therefore is not a feasible route. 
         [0092]    Both solo routes and direct routes may also be described using travel metrics other than time. 
         [0093]    In one or more embodiments, “direct efficiency” may be defined as a ratio between the passenger travel metrics measured along a given passenger&#39;s direct route, to vehicle travel metrics taken along a feasible route including that passenger. 
         [0094]    In one or more embodiments, “solo efficiency” may be defined as a ratio between the passenger travel metrics measured along a given passenger&#39;s solo route, to vehicle travel metrics taken along a feasible route including that passenger. 
         [0095]    Particular Embodiments 
         [0096]    Certain of the embodiments include use of a given method (FIG. A,  201 ) used to find a suitable or superior route given a vehicle(s)  300 , passenger(s)  100  and respective origin(s) and destination(s), and map(s)  202 . 
         [0097]    In one or more embodiments, the method may incorporate one or more vehicles  300  equipped as described in section [C] of the description, and a dispatch unit  200  as described in section [B] of the description. 
         [0098]    In one or more embodiments, it is assumed that one or more vehicles  300  are available for service, and that they have recently communicated their positions to the dispatch unit  200 . Moreover, it is assumed that one or more parties of travelers  100  have (or will have) communicated with the dispatch unit  200 , informing it of their origin, their desired destination, and their wish to travel. 
         [0099]    In some embodiments, the party of travelers  100  may further inform the dispatch unit  200  of the number of travelers in the party  100 , or other information affecting routing, such as the party&#39;s status as a premier customer requiring swifter service. 
         [0100]    In one or more embodiments, the routing method  201  may use the information received from the traveling parties  100 , the positions of the vehicles  300 , and the map  202  information to produce one set of feasible routes or more than one sets of feasible routes, with each feasible route within any such set of feasible routes connecting at least one traveling party  100  to a vehicle  300 . In one or more embodiments, the routing method  201  shall choose one set of feasible routes as superior to the others, and the dispatch unit  200  shall communicate each feasible route within that set to the vehicle  300  associated with that feasible route. 
         [0101]    In one or more embodiments, the routing method  201  may consider a set of routes to be superior if it produces the lowest total passenger travel cost, total passenger travel cost being the sum of passenger travel costs along all feasible routes in set of routes. 
         [0102]    In one or more embodiments, the routing method  201  may consider a set of routes to be superior if it produces the lowest total vehicle travel cost, total vehicle travel cost being the sum of all vehicle travel costs along all feasible routes in the set of routes. 
         [0103]    In one or more embodiments, the routing method  201  may add or combine total passenger travel costs and total vehicle travel costs, and deem any route set with the lowest combined travel cost to be superior to other route sets. 
         [0104]    In one or more embodiments, the routing method  201  may calculate the overall direct efficiency of all routes in a route set, and deem any route set with the highest overall direct efficiency to be superior to other route sets. 
         [0105]    In one or more embodiments, the routing method  201  may calculate the overall solo efficiency of all routes in a route set, and deem any route set with the highest overall solo efficiency to be superior to other route sets. 
         [0106]    0— FIG. 0  and Table 0 illustrate an example of a simple such embodiment, and serve to elucidate the notation that will be used in subsequent embodiments. For this example, the routing method is using time as the travel metric, and using the criteria of least passenger travel cost to select the best route set. In this case, a single car X 1  is available to serve a single party at point (A), traveling to point (a). The feasible route is indicated by a dotted, curved line, and the travel metrics along the feasible route (be they time, distance, or money) are numeric labels embedded in the straight, solid lines. The route shown can be defined as X 1 -&gt;A-&gt;a, indicating a feasible route served by car X 1 , proceeding to point (A), then to point (a). The leftmost column in Table 0 (headed “Position(X 1 )”, for the position of car X 1 ), read from top to bottom, will perforce have entries X 1 , A, and a, in that order. To the right of that column are a set of columns headed with the “name” of the traveling party. In this case only one passenger exists, passenger (A). Beneath that header are numbers that indicate the amount of the given travel metric that the passenger will have spent enroute up to reaching this point. For example, the first entry under column A is 0, which is the amount of time that passenger (A) is forecast to have spent enroute when the car is at point (X 1 ). The next entry in column A is 1, which is the amount of time passenger (A) is forecast to have spent enroute when his vehicle arrives at point (A), and the last entry is 5, the total amount passenger (A) will spend enroute before his vehicle arrives at a, which is his destination, after which point passenger (A) will not accrue any further time. Another column shows the time spent enroute for the vehicle, which in this simple example happens to be equal to the time enroute of the passenger. The sum of the passenger&#39;s times (or other travel metric) spent enroute, plus in some cases the vehicles time(s) enroute, are used to select superior sets of feasible routes in some embodiments. In some embodiments, either the vehicle(s) time or the passenger(s) time may not be used to calculate fitness of a feasible route, in which case it may be omitted. In this example, only one feasible route exists, and the vehicle will be dispatched accordingly. In such an embodiment, the method may use travel metrics other than time. 
         [0107]    1— FIGS. 1 and 2  are diagrams illustrating another example of an embodiment. For this example, the routing method is using time as the travel metric, and using the criteria of least passenger travel cost to select the best route set. In this example, a passenger at point (A) in  FIG. 1  notifies a service bearing a dispatch unit that he desires to move to point (a), and likewise a passenger at point (B) notifies the same dispatch unit of his desire to go to point (b). The dispatch unit, having an electronic map covering the area and showing estimated travel times between points therein, and having received location information from a vehicle X 1  at the point X 1 , plots a preliminary feasible route to serve both passengers. This feasible route may involve car X 1  picking up the first passenger at point (A), requiring in this example one minute to arrive: then to proceed to point (a) to drop him off, requiring four additional minutes: then to point (B) to get the second passenger, using an additional five minutes: then to point (b) to disembark him and complete the task, taking an additional four minutes. The passenger (A) starting at point (A) would be enroute for a total of five minutes, and the passenger (B) starting at point (B) would be enroute for a total of 14 minutes, for a total of 19 minutes enroute for both passengers. Such a feasible route may hereafter for brevity be described thus: 
         [0108]    X 1 -&gt;A-&gt;a-&gt;B-&gt;b. 
         [0109]    The times required are shown in Table 1. 
         [0110]    In  FIG. 2 , the system has computed a different feasible route for the same two rides, X 1 -&gt;A-&gt;B-&gt;b-&gt;a, requiring seven minutes for the passenger starting at point (A) and six for the passenger starting at point (B), a total of 13 minutes, as shown in Table 2. In this case, the second feasible route would be deemed superior on the grounds of its smaller total passenger costs enroute, a superior set of feasible routes would be generated (in this case the set will have only one feasible route), and the vehicles would be dispatched accordingly. 
         [0111]    2— FIGS. 3 and 4  are diagrams illustrating another example of such an embodiment. For this example, the routing method is using time as the travel metric, and using the criteria of least passenger travel cost to select the best route set. In this example, a passenger at point (A) notifies a service bearing a dispatch unit that is itself in communication with two vehicles that he desires to move to point (a). The dispatch unit, using its maps and methods as previously described, generates a feasible route using car X 2  ( FIG. 3 , Table 3). It then generates another feasible route involving car X 1  ( FIG. 4 , Table 4). The method calculates that the passenger will suffer a smaller time enroute if he is carried by car X 1  rather than car X 2 . A set of feasible routes is generated, in this example containing only aforesaid single route, and car X 1  is therefore dispatched to transport the passenger, and car X 2  is not involved. In such an embodiment, the method may use travel metrics other than time. 
         [0112]    3— FIGS. 5 and 6  are diagrams illustrating another example of such an embodiment. For this example, the routing method is using time as the travel metric, and using the criteria of least passenger travel cost to select the best route set. In this example, two passengers at points (A) and (B) notify a service with a dispatch unit that they wish to travel to point (a) and point (b), respectively. The service is in contact with two cars, X 1  and X 2 . The service may initially choose the set containing only feasible route X 1 -&gt;A-&gt;a-&gt;B-&gt;b, that is, with car X 1  handling both passengers and with car X 2  uninvolved. This method yields a total time enroute of 13, as shown in  FIG. 5  and described in Table 5. The service may also choose another set of feasible routes as in  FIG. 6  and Table 6, X 1 -&gt;A-&gt;a and X 2 -&gt;B-&gt;b, yielding total time enroute of 10, which would be deemed superior to the first route set&#39;s total of 13. The second route set would be chosen, and the vehicles would be dispatched to carry each of their respective passengers, X 1  carrying passenger (A) and X 2  carrying passenger (B). In such an embodiment, the method may use travel metrics other than time. 
         [0113]    4—In one or more embodiments, the method may examine money costs of travel along a given route and choose as superior a route yielding a lower sum total money cost for all passengers and vehicles. Here again, we can use  FIGS. 1 and 2  and Tables 1 and 2, with the travel metric of time replaced by the travel metric of money costs accrued enroute. This may be useful in dealing with, for example, toll roads or tolled bridges. The method would again select the set of feasible routes with the lowest sum of relevant travel metrics, and dispatch the vehicles accordingly. 
         [0114]    5—In one or more embodiments, the method may choose to weigh the time spent by a given passenger more heavily than the time spent by another. For example, if a given passenger has paid for premium service, the method may choose to count every minute he spends enroute five times, effectively weighting his time by a factor of five. The method may then choose a set of feasible routes having a lower sum of passenger travel time for all persons traveling.  FIGS. 7 and 8  illustrate such an example. In this example the time enroute of the passenger starting at point (A) is multiplied by a factor of 5, as shown in Tables 7 and 8. The superior feasible route set (in FIG.  7 /Table 7) shall be chosen on the basis of lower total (weighted) time enroute, and the vehicles dispatched accordingly. As in other embodiments, the method may use travel metrics other than time. Alternatively, such an embodiment could 
         [0115]    6—In one or more embodiments, the method may convert between units of money, distance, or time, and choose a set of feasible routes having a lower sum total of whatever travel metric is in use. For example, the provider may choose to define ten dollars as being worth exactly one hour. For a route crossing a bridge charging a toll of five dollars, one half hour is added to the time required to cross that bridge for the purposes of the method. To give another example, if the method is using units of distance, and sets one kilometer equal to one dollar, the five dollar bridge toll is converted to five kilometers, which is added to the distance along that leg for purpose of computation of sum total of distance enroute. The method will deem superior any set of feasible routes having a smaller sum total of whatever travel metric is in use, and the vehicles would be dispatched accordingly. 
         [0116]    7—In one or more embodiments, the method may choose to weight certain portions of the journey more or less heavily than others, by multiplying or dividing the travel metric used along that portion by some number. For example, the method may weight time spent waiting for a vehicle to arrive twice as heavily as time spent riding in the vehicle, and would multiply such waiting time by a factor of two(or some other value), while time spent in the vehicle is unchanged. The method would sum the time for all passengers served, and choose a superior route set on the basis of lesser sum total time enroute. To take another example, the method may determine that costs delivering over dirt roads are higher than costs over paved roads, and would multiply money costs of traveling over such roads by a factor of (for example) 1.5, converting costs into time on an hours-per-dollar basis, and adding the time so derived to the time enroute of all other passengers and/or vehicles served, and choosing a superior route set on the basis of lesser sum total time enroute, and dispatching the vehicles accordingly. In such an embodiment, the method may use travel metrics other than time. 
         [0117]    8—In one or more embodiments, the method may choose to multiply the time (or other suitable travel metric) enroute for a given party of persons traveling together (that is, from the same origin to the same destination) by the number of persons in the party, for the purposes of selecting a superior set of feasible routes. A route set with a lower total time enroute for all passengers would be deemed superior, and vehicles would be dispatched accordingly. This is illustrated in  FIGS. 9 and 10  and Tables 9 and 10. In this case, we assume that ride (B) comprises two people traveling together. The first feasible route set generated contains only route X 1 -&gt;B-&gt;A-&gt;a-&gt;b, which produces a total time enroute of  20  (Table 9). The second feasible route set generated contains only route X 1 -&gt;A-&gt;B-&gt;b-&gt;a, which produces a total time enroute of 19(Table 10). The second route set, having a lower total time enroute, would be deemed superior, and the cars dispatched accordingly. In such an embodiment, the method may use travel metrics other than time. 
         [0118]    9—In one or more of the embodiments, the method may choose to include the time or distance covered by the vehicle(s) and driver(s), or money costs accrued by same, as it would the passenger(s), before choosing a route set on the basis of least total time or distance, as above. This may be useful in cases where the driver wishes to go off-duty at a particular location, in which case he would order a ride on his own vehicle, knowing that his desire to get to his own destination will be weighed against the passengers&#39; desire to go to their own destinations. In this embodiment, the method will add the travel metric incurred by the driver along any given feasible route to that incurred by all passengers along the same feasible route, and that of any other drivers and passengers in the same route set, to yield a total of time or distance covered by the involved persons. The method shall deem superior any such route set having a lesser total than any comparable route set, and the vehicles would be dispatched accordingly. As in other embodiments, any travel metric or combination thereof may be utilized. 
         [0119]    10—It may be a feature of one or more embodiments that passengers desiring rides that are approximately equally efficient (using the definition of “direct efficiency” given above) may tend to be served in approximately the same amount of time. This has the advantage of allocating the transportation resource fairly among passengers that are more or less equally profitable to serve. This can be seen in  FIG. 1  and  FIG. 2 , and described in Tables 1 and 2. The direct route for passenger (A) measures 4 by whatever travel metric is in use (that is, the distance between origin and destination is 4 units), and the direct route for passenger (B) also measures 4. Each of the passengers can be served along his respective direct route by a vehicle traveling along 5 units, so the efficiency of the passengers is equal at 0.8 (=4/5). The first route set chosen in FIG. 1 has passenger (A) arriving in 5 units of time and passenger (B) in 14 units of time, but after choosing a superior route set, their respective measures are 7 and 6 units of time, which are more nearly equal. This relative equality is a desirable side effect of the routing method. 
         [0120]    11—It may be a feature of one or more embodiments that a passenger that is less efficient (using the definition of “direct efficiency” given above) to serve is usually served later than other passengers. An example of such an embodiment is illustrated in  FIGS. 11 and 12 , and described in Tables 11 and 12. In this example, the two passengers at point (A) and point (B) may be carried by the car at X 1 , but one passenger is more efficient to serve: Passenger (A) has a direct route 1 unit long, and requires the car to be enroute for 5 units to serve it. yielding a direct efficiency of 0.20 (1/5). whereas B. with a direct route of 4 units and a vehicle time enroute of 5 has a superior direct efficiency of 0.8 (4/5). It should be noted that the route shown in  FIG. 12  and described in Table 12 shows a lower sum total time enroute for both passengers (14=9+5) than does the route in  FIG. 11  and Table 11 (19=5+14), and also shows a larger time enroute (and later delivery) for the less efficient passenger (A). This is desirable because it provides better service to passengers that are more profitably served. In this embodiment, the route set having the smaller sum total time enroute would be deemed superior, and the vehicle(s) would be dispatched accordingly, harvesting the provision of faster service to the more efficient passenger as a desirable side effect of the routing method. 
         [0121]    12—It may be a feature of one or more embodiments that a passenger may be carried to his destination even if his vehicle suffers a mechanical breakdown or other disability enroute. Consider for example a case in which a dispatch unit is in contact with two or more vehicles, X 1  and X 2 . A party (A) books a ride from point (A) to point (a), and car X 1  is dispatched to carry the party. After embarking passenger (A) at point (A), the vehicle suffers a disability at some point (Z) rendering it unable to continue. The vehicle may notify the dispatch unit of the disability and of its current position at point (Z), and the dispatch unit may record the fact that that particular vehicle is unable to carry passengers, and that the passenger has disembarked at point (Z). The dispatch unit, which may have previously recorded the fact of embarkation, may generate another ride for that passenger from point (Z) to point (a) , and may route and dispatch the ride through one of the methods described in these embodiments, excluding the disabled vehicle from candidacy to carry the passenger. In this example, vehicle X 2  may be routed and dispatched to handle the ride. 
         [0122]    13—It may be a feature of one or more embodiments that a new vehicle becoming active may be used to deliver passengers who have already booked rides and have had those rides dispatched and/or embarked when the second vehicle becomes active.  FIGS. 13 ,  14 , and  15 , along with Tables 13, 14, and 15 illustrate an example of such an embodiment. In  FIG. 13 , passenger (A) and passenger (B) have booked rides to point (a) and point (b) respectively, and car X 1 , the only car available, has been dispatched to serve them. The initial routes are as described in Table 13. Car X 1  embarks passenger (A) and begins traveling to point (B). When it is at point (Z)[see  FIG. 14 ], a second car X 2  becomes available, whereupon the dispatch unit is faced with a choice of using X 1  to carry both riders, as originally planned, or to employ car X 2  to carry passenger (B) [passenger (A) is already on board car X 1 ]. This situation may be reduced to that shown in  FIGS. 14 and 15 . The dispatch unit may initially calculate the sum of times enroute from the moment at which car X 1  is at point (Z) forward for all passengers if car X 1  is used to carry both rides as originally planned. This circumstance is shown in  FIG. 14  and in Table 14, and shows that total times enroute for both passengers from that moment forward (that is, not counting time already accrued) add up to 12 units[=7 for passenger (A)+5 for passenger (B)]. The dispatch unit may generate another set of feasible routes from the same moment forward, using car X 2  to transport passenger (B), and as shown in  FIG. 15  and Table 15, this route will produced a sum of time enroute from that moment forward of 10 units (=5 for A+5 for B). In such an example, the method will deem the second route set to be superior, and will direct car X 1  to change directions at point (Z), proceeding directly to point (a) to disembark passenger (A), and X 2  will be directed to point (B) to embark passenger (B), then to point (b) to disembark him, completing both rides. It should be clear that the same method may be used to reroute vehicles that have not yet embarked passengers—the method may generate one or more feasible routes from the point at which the new vehicle becomes available, calculate total times enroute for all passengers for each route from that moment forward, select a winning route set based on lowest sum total time enroute from that moment forward, and dispatch the vehicles accordingly. As in other embodiments, the method may also employ travel metrics other than time. 
         [0123]    14—It may be a feature of one or more embodiments that a new ride unexpectedly booked by a heretofore unknown passenger may be handled by an active vehicle, perhaps even one already containing passengers on other rides. Consider an example shown in  FIG. 16 , in which car X 1  has been dispatched to carry a passenger from point (A) to point (a), passing an invisible point (Z) on the way from point (A) to point (a).  FIG. 17  shows the situation when passenger (A) has already embarked at point (a) and the vehicle has reached point (Z), at which time a second passenger books a ride from point (B) to point (b). The dispatch unit may then calculate any feasible routes beginning at point (Z). Two such routes are shown in  FIGS. 17 and 18 , and they are likewise described in Tables 17 and 18. In this example, the method will choose the routes in Table 18, Z-&gt;B-&gt;a-&gt;b as being the best of these two feasible route sets on the grounds that it shows a lower sum total time enroute from point (Z) forward. Notice that passenger (B) will embark before passenger (A) disembarks in this example. As usual, the dispatch unit may use a travel metric other than time to make its calculations. 
         [0124]    15—It may be a feature of one or more embodiments that a passenger may be delivered to a hub, at which point he will disembark and subsequently embark upon another vehicle to continue his ride. Such an embodiment is illustrated in  FIGS. 19 and 20 , and described in Tables 19 and 20. Assume for the sake of the example that two rides A and B are booked.  FIG. 19  illustrates how such rides may be served without the use of a hub: 
         [0125]    Route Set 1:
       Car X 1  follows the route:
           X 1 -&gt;A-&gt;B-&gt;(bypasses the hub)-&gt;a-&gt;(bypasses the hub)-&gt;b   
           Car X 2  is not employed in this route set.   As Table 19 shows, this routing will require a total of 10 minutes enroute to be borne by the passengers, and 6 minutes by the vehicles.       
 
         [0130]    Using a hub as illustrated in  FIG. 20 , such rides may be served more efficiently as follows: 
         [0131]    Route Set 2:
       Car X 1  follows the route:
           X 1 -&gt;A-&gt;B-&gt;(stops at hub, disembarks party B)-&gt;a   
           Car X 2  follows the route:
           X 2 -&gt;(stops at hub)-&gt;(awaits party B traveling on X 1  for 1 minute)-&gt;(embarks passenger B)-&gt;b   
               
 
         [0136]    As Table 20 shows, this routing will require a total of 8 minutes enroute to be borne by the passengers, and 8 minutes by the vehicles. 
         [0137]    It should be clear that the vehicles and passengers may transit any number of hubs, and that any number of passengers may be handled in this manner. Moreover, the method may use any travel metric or combination of travel metrics in determining efficiency, and may weight the time spent by passengers or vehicles at the hub for use in calculating efficiency, or discount it entirely. Moreover, the method may or may not use the time, distance, or money spent by the vehicles in serving rides when calculating efficiency for such an embodiment. In the illustrated example, the travel metric used is time, and the method seeks to minimize passenger travel time, so the second route set would be deemed superior on the grounds of least total time enroute, and the vehicles dispatched accordingly. On the other hand, if the method seeks to minimize total vehicle cost, the first route set would be deemed superior to the second. As in other embodiments, the method may employ travel metrics other than time. 
         [0138]    16—It may be a feature of one or more embodiments that the dispatch unit may be informed of the number of empty seats in a vehicle when the vehicle has no passengers, and may calculate and keep a count of empty seats at every point along a vehicles&#39; proposed route. It may further be a feature of such embodiments that the dispatch unit will subtract one empty seat for each actual or forecasted embarkation of a passenger, and may add one empty seat for every such actual or forecasted disembarkation of a passenger. Moreover, it may further be a feature of such embodiments that the dispatch unit will require that a vehicle never has less than zero empty seats along any feasible route, and that any route violating this constraint is deemed infeasible. 
         [0139]    17—In one or more embodiments, the method may consider a set of routes to be superior if it produces the highest overall direct efficiency, as such is defined above.  FIGS. 1 and 2 , along with Tables 1 and 2, illustrate an example of such an embodiment. The route set shown in  FIG. 1  has a direct traveler cost of 8 units (4 for each of the parties) and a vehicle travel cost of 14 (the metrics along the length of the path taken by the single vehicle involved), a ratio of 8/14, or about 0.57. The route set in  FIG. 2  also has a direct traveler cost of 8 (for the same reasons as in  FIG. 1 ), but a vehicle travel cost of 7, yielding a larger and therefore superior direct efficiency of 8/7 (about 1.14) for the second route set. In such an instance, the second route set may be chosen, and the vehicles dispatched accordingly. Note carefully that the highest overall direct efficiency is equivalent to the lowest ratio of the total vehicle travel cost to total direct traveler cost. 
         [0140]      18 —In one or more embodiments, the method may consider a set of routes to be superior if it produces the highest overall solo efficiency, as such is defined above.  FIGS. 1 and 2 , along with Tables 1 and 2, illustrate an example of such an embodiment. The route set shown in  FIG. 1  has a sum of vehicle travel costs of 14 units. The solo traveler costs are each  5 , taken along route X 1 -&gt;A-&gt;a for passenger (A) and X 1 -&gt;B-&gt;b for passenger (B), so the total of solo traveler cost is 10, and the ratio is 10/14 (about 0.714). In  FIG. 2 , the travelers&#39; solo costs are the same as in  FIG. 1 , but the vehicle travel cost is now 7 and the ratio is 10/7 (about 1.428). The second route set would be deemed superior, and the vehicles dispatched accordingly. Note carefully that highest overall solo efficiency is equivalent to lowest ratio of the total vehicle travel cost to total solo traveler cost.