# US 2018/0322441 A1 · Efficient optimization of schedules in a public transportation system

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

- Number: US 2018/0322441 A1
- Document ID: US20180322441A1
- Status: Published application
- Kind: A1
- Application number: 15/587,761
- Filed: 2017-05-05
- Published: 2018-11-08
- Earliest claimed: 2017-05-05
- Assignees: Conduent Business Services, LLC
- Applicants: Conduent Business Services, LLC
- Inventors: Sofia Zaourar-Michel
- Web page: https://patentgrep.com/patent/US20180322441A1

## CPC

- G06Q 10/063116: {Schedule adjustment for a person or group}
- 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

## Abstract

Methods and systems are disclosed for optimizing public transportation schedules. Shifts from current schedules associated with a public transportation system can be evaluated. The impact on waiting times can then be determined, based on evaluating the shifts from the current schedules. Schedules associated with the public transportation system are then optimized based on the impact on the waiting times. Public transport schedules can thus be optimized by minimizing the waiting time during, for example, transfers. Using ticket validation data to construct a realistic scenario-based model of the waiting times, a goal of this approach is to compute shifts of the current schedules that reduce the overall expected waiting time.

## Claims

### Claim 1

A method for optimizing public transportation schedules, said method comprising:
evaluating shifts from current schedules associated with a public transportation system;
determining an impact on waiting times based on said evaluating of said shifts from said current schedules; and
optimizing schedules associated with said public transportation system based on said impact on said waiting times.

### Claim 2 (depends on 1)

The method of claim 1 wherein said evaluating said shifts from said current schedules further comprises:
exploring random shifts from said current schedules utilizing a parallel local search.

### Claim 3 (depends on 2)

The method of claim 2 wherein said parallel heuristic search produces parallel heuristic search results.

### Claim 4 (depends on 1)

The method of claim 1 wherein said evaluating shifts from said current schedules associated with said public transportation system, further comprises:
finding a shift of each transit trip among a plurality of transit trips associated with said current schedules so as to minimize an expected transfer waiting time among said waiting times.

### Claim 5 (depends on 1)

The method of claim 1 wherein evaluating shifts from current schedules associated with a public transportation system, further comprises:
randomly selecting a subset of trips among a plurality of transit trips associated with said current schedules to offset;
randomly selecting a perturbation of said offset within an adequate boundary; and
evaluating an impact of said offset.

### Claim 6 (depends on 5)

The method of claim 5 wherein optimizing said schedules further comprises updating a best schedule among said schedules.

### Claim 7 (depends on 5)

The method of claim 5 further comprising running parallel instances with different seeds.

### Claim 8

A system for optimizing public transportation schedules, said system comprising:
at least one processor, and
a non-transitory computer-usable medium embodying computer program code, said computer-usable medium capable of communicating with said at least one processor, said computer program code comprising instructions executable by said at least one processor and configured for:
evaluating shifts from current schedules associated with a public transportation system;
determining an impact on waiting times based on said evaluating of said shifts from said current schedules; and
optimizing schedules associated with said public transportation system based on said impact on said waiting times.

### Claim 9 (depends on 8)

The system of claim 8 wherein said instructions for evaluating said shifts from said current schedules further comprises instructions configured for exploring random shifts from said current schedules utilizing a parallel local search.

### Claim 10 (depends on 9)

The system of claim 9 wherein said parallel heuristic search produces parallel heuristic search results.

### Claim 11 (depends on 8)

The system of claim 8 wherein said instructions for evaluating shifts from said current schedules associated with said public transportation system further comprise instructions configured for finding a shift of each transit trip among a plurality of transit trips associated with said current schedules so as to minimize an expected transfer waiting time among said waiting times.

### Claim 12 (depends on 8)

The system of claim 8 wherein said instructions for evaluating shifts from current schedules associated with a public transportation system, further comprises instructions configured for:
randomly selecting a subset of trips among a plurality of transit trips associated with said current schedules to offset;
randomly selecting a perturbation of said offset within an adequate boundary; and
evaluating an impact of said offset.

### Claim 13 (depends on 12)

The system of claim 12 wherein said instructions for optimizing said schedules further comprise instructions configured for updating a best schedule among said schedules.

### Claim 14 (depends on 12)

The system of claim 12 further comprising instructions configured for running parallel instances with different seeds.

### Claim 15

A non-transitory processor-readable medium storing computer code representing instructions to cause a process for optimizing public transportation schedules, said computer code comprising code to:
evaluate shifts from current schedules associated with a public transportation system;
determine an impact on waiting times based on said evaluating of said shifts from said current schedules; and
optimize schedules associated with said public transportation system based on said impact on said waiting times.

### Claim 16 (depends on 15)

The non-transitory processor-readable medium of claim 15 wherein said code to evaluate said shifts from said current schedules further comprises code to explore random shifts from said current schedules utilizing a parallel local search.

### Claim 17 (depends on 16)

The non-transitory processor-readable medium of claim 16 wherein said parallel heuristic search produces parallel heuristic search results.

### Claim 18 (depends on 15)

The non-transitory processor-readable medium of claim 15 wherein said code to evaluate shifts from said current schedules associated with said public transportation system further comprises code to find a shift of each transit trip among a plurality of transit trips associated with said current schedules so as to minimize an expected transfer waiting time among said waiting times.

### Claim 19 (depends on 15)

The non-transitory processor-readable medium of claim 15 wherein said code to evaluate shifts from current schedules associated with a public transportation system, further comprises code to:
randomly select a subset of trips among a plurality of transit trips associated with said current schedules to offset;
randomly select a perturbation of said offset within an adequate boundary; and
evaluate an impact of said offset.

### Claim 20 (depends on 19)

The non-transitory processor-readable medium of claim 19 wherein said code to optimize said schedules further comprises code for updating a best schedule among said schedules.
