# US 2012/0253657 A1 · System and method for itinerary planning

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2012/0253657 A1
- Document ID: US20120253657A1
- Status: Published application
- Kind: A1
- Application number: 13/432,812
- Filed: 2012-03-28
- Published: 2012-10-04
- Earliest claimed: 2011-03-28
- Assignees: Trapeze Software Inc.
- Inventors: Matthew David FRANCIS
- Web page: https://patentgrep.com/patent/US20120253657A1

## CPC

- G06Q 10/025: {Coordination of plural reservations, e.g. plural trip segments, transportation combined with accommodation}
- G01C 21/3423: {Multimodal routing}
- G01C 21/3446: {Details of route searching algorithms, e.g. Dijkstra, A*, arc-flags or using precalculated routes}
- G06Q 10/047: Optimisation of routes or paths, e.g. travelling salesman problem
- G06Q: INFORMATION AND COMMUNICATION TECHNOLOGY [ICT] SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES; SYSTEMS OR METHODS SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES, NOT OTHERWISE PROVIDED FOR
- G01C: MEASURING DISTANCES, LEVELS OR BEARINGS; SURVEYING; NAVIGATION; GYROSCOPIC INSTRUMENTS; PHOTOGRAMMETRY OR VIDEOGRAMMETRY (measuring liquid level G01F; radio navigation, determining distance or velocity by use of propagation effects, e.g. Doppler effects, propagation time, of radio waves, analogous arrangements using other waves G01S)

## Abstract

The present invention relates to a system and method for itinerary planning. The method commences with the population of a first queue with a first set of network segments connected to the origin. One of the network segments is removed from the first queue. An expansion build representing the one network segment removed from the input queue is placed together with a continuing network segment in a second queue if the continuing network segment has not been considered. A captured build representing the network segment removed from the input queue together with the continuing network segment in the first queue if the continuing network segment has been considered. The placing is repeated until the first queue is empty. The first queue is replaced with the builds in the second queue. The removing to the replacing is repeated until the first and second queues are empty. At least one of the builds having a lowest cost is outputted.

## Claims

### Claim 1

A method for itinerary planning, comprising:
populating a first queue with a first set of network segments connected to the origin;
removing one of said network segments from said first queue;
placing an expansion build representing said one network segment together with a continuing network segment in a second queue if said continuing network segment has not been considered;
placing a captured build representing said one network segment together with said continuing network segment in said first queue if said continuing network segment has been considered;
repeating said placing until said first queue is empty;
replacing said first queue with said builds in said second queue;
repeating said removing to said replacing steps until said first and second queues are empty; and
outputting at least one of said builds having a lowest cost.

### Claim 2 (depends on 1)

The method of claim 1, wherein said placing said expansion segment comprises:
placing said expansion build in said second queue if a best possible outcome for said expansion build is less than or equal to a threshold value; and
placing said expansion build in a third queue if said best possible outcome for said expansion build is greater than said threshold value,
and wherein said repeating said removing comprises:
repeating said removing to said replacing steps until said first, second and third queues are empty.

### Claim 3 (depends on 2)

The method of claim 2, further comprising:
replacing said first queue with said third queue when said first and second queues are empty.

### Claim 4 (depends on 3)

The method of claim 3, wherein replacing said first queue further comprises:
adjusting said threshold.

### Claim 5 (depends on 1)

The method of claim 1, wherein said placing said expansion build comprises:
placing said expansion build representing said one network segment together with a continuing network segment in a second queue if said continuing network segment has not been considered and if the cost to arrive at the end of said expansion build is better than the cost previously determined for arriving at the end of said continuing network segment.

### Claim 6 (depends on 1)

The method of claim 1, wherein said placing said captured build comprises:
placing a captured build representing said one network segment together with said continuing network segment in said first queue if said continuing network segment has been considered and if the cost to arrive at the end of said captured build is better than the cost previously determined for arriving at the end of said continuing network segment.

### Claim 7 (depends on 1)

The method of claim 1, further comprising:
noting the cost of said build if said continuing network segment arrives at the destination.

### Claim 8

A system for itinerary planning, comprising:
a database of network segments;
a processor executing computer-executable instructions for analyzing said network segments and, in response to an itinerary planning request, populating a first queue with a first set of network segments connected to the origin, removing one of said network segments from said first queue, placing an expansion build representing said one network segment together with a continuing network segment in a second queue if said continuing network segment has not been considered, placing a captured build representing said one network segment together with said continuing network segment in said first queue if said continuing network segment has been considered, repeating said placing until said first queue is empty, replacing said first queue with said builds in said second queue, and repeating said removing to said replacing steps until said first and second queues are empty, and outputting at least one of said builds having a lowest cost.

### Claim 9 (depends on 8)

The system of claim 8, wherein said processor places said expansion build in said second queue if a best possible outcome for said expansion build is less than or equal to a threshold value, places said expansion build in a third queue if said best possible outcome for said expansion build is greater than said threshold value, and repeats said removing to said replacing steps until said first, second and third queues are empty.

### Claim 10 (depends on 9)

The system of claim 9, wherein said processor replaces said first queue with said third queue when said first and second queues are empty.

### Claim 11 (depends on 10)

The system of claim 10, wherein said processor adjusts said threshold when replacing said first queue with said second queue.

### Claim 12 (depends on 8)

The system of claim 8, wherein said processor places said expansion build representing said one network segment together with a continuing network segment in a second queue if said continuing network segment has not been considered and if the cost to arrive at the end of said expansion build is better than the cost previously determined for arriving at the end of said continuing network segment.

### Claim 13 (depends on 8)

The system of claim 8, wherein said processor places a captured build representing said one network segment together with said continuing network segment in said first queue if said continuing network segment has been considered and if the cost to arrive at the end of said captured build is better than the cost previously determined for arriving at the end of said continuing network segment.

### Claim 14 (depends on 8)

The system of claim 8, wherein said processor notes the cost of said network build if said continuing network segment arrives at the destination.

### Claim 15

A method for itinerary planning, comprising:
generating builds of network segments for a journey, said network segments being stored in a database in storage of a computer system;
placing said builds that whose last network segment has been previously considered in a first queue;
placing said builds whose last network has been previously unconsidered in a second queue;
expanding said builds in said first queue before expanding said builds in said second queue; and
outputting at least one of said builds arriving at a destination for said journey having a lowest cost.

### Claim 16 (depends on 15)

The method of claim 15, wherein said placing said builds in said second queue comprises:
placing said builds in said second queue if a best possible outcome for said builds is less than or equal to a threshold value; and
placing said builds in a third queue if said best possible outcome for said builds is greater than said threshold value.

### Claim 17 (depends on 16)

The method of claim 16, further comprising:
replacing said first queue with said second queue when said first queue is empty.

### Claim 18 (depends on 17)

The method of claim 17, further comprising:
replacing said first queue with said third queue when said first and second queues are empty.

### Claim 19 (depends on 18)

The method of claim 18, wherein replacing said first queue further comprises:
adjusting said threshold.
