# US 2019/0295036 A1 · Method and apparatus for planning route

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

- Number: US 2019/0295036 A1
- Document ID: US20190295036A1
- Status: Published application
- Kind: A1
- Application number: 16/269,182
- Filed: 2019-02-06
- Published: 2019-09-26
- Earliest claimed: 2018-03-22
- Assignees: Beijing Baidu Netcom Science Technology Co., Ltd.
- Applicants: Beijing Baidu Netcom Science and Technology Co., Ltd.
- Inventors: Junxiang FAN
- Web page: https://patentgrep.com/patent/US20190295036A1

## CPC

- G06Q 10/08355: {Routing methods}
- G06Q 10/047: Optimisation of routes or paths, e.g. travelling salesman problem
- G06Q 30/0284: {Time or distance, e.g. usage of parking meters or taximeters}
- 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

Embodiments of the present disclosure disclose a method and apparatus for planning a route. A specific embodiment of the method includes: acquiring task information; generating initial route information based on the task information; performing the updating step including: updating the second sequence in the second sequence set based on a preset rule; updating the first sequence in the first sequence set based on the updated second sequence set; and determining a delivery cost of the delivery unit based on the updated first sequence set and the updated second sequence set; and the method further includes: determining, based on the updated first sequence set and the updated second sequence set, a route of the to-be-delivered items delivered from the initial node to the destination node via the intermediate node, in response to the determined delivery cost meeting a preset delivery cost condition.

## Claims

### Claim 1

A method for planning a route, the method comprising:
acquiring task information, the task information comprising a location of an initial node where to-be-delivered items are located, a location of a destination node of the to-be-delivered items, and a location of an intermediate node between the initial node and the destination node;
generating initial route information based on the task information, the initial route information comprising a first sequence set and a second sequence set, the first sequence set comprising at least one first sequence, the first sequence being used to indicate a route of a delivery unit delivering the to-be-delivered items from the initial node to one of the intermediate node, the second sequence set comprising at least one second sequence, and the second sequence being used to indicate a route of the delivery unit delivering the to-be-delivered items from one of the intermediate node to the destination node of the to-be-delivered items;
performing an updating step comprising:
updating the second sequence in the second sequence set based on a preset rule; updating the first sequence in the first sequence set based on the updated second sequence set; and determining a delivery cost of the delivery unit based on the updated first sequence set and the updated second sequence set; and
determining, based on the updated first sequence set and the updated second sequence set, a route of the to-be-delivered items delivered from the initial node to the destination node via the intermediate node, in response to the determined delivery cost meeting a preset delivery cost condition.

### Claim 2 (depends on 1)

The method according to claim 1, wherein the generating initial route information based on the task information comprises:
generating the second sequence in the second sequence set based on the task information using a large-scale neighborhood search algorithm;
determining, based on the generated second sequence, item information of the to-be-delivered items to be stored by each intermediate node; and
generating the first sequence in the first sequence set based on the determined item information using the large-scale neighborhood search algorithm.

### Claim 3 (depends on 1)

The method according to claim 1, wherein the updating the second sequence in the second sequence set based on a preset rule comprises:
removing randomly a predetermined number of the destination node comprised in the second sequence in the second sequence set to obtain a third sequence set, and adding randomly the removed destination node to a third sequence in the third sequence set to generate the updated second sequence set.

### Claim 4 (depends on 1)

The method according to claim 1, wherein the updating the first sequence in the first sequence set based on the updated second sequence set comprises:
determining, based on the updated second sequence set, item information of the to-be-delivered item to be stored by the intermediate node; and
generating the first sequence in the first sequence set based on the determined item information using a large-scale neighborhood search algorithm.

### Claim 5 (depends on 3)

The method according to claim 3, wherein after determining a delivery cost of the delivery unit based on the updated first sequence set and the updated second sequence set, the updating step further comprise:
determining the delivery cost of the delivery unit determined based on the updated first sequence set and the updated second sequence set as the target delivery cost, in response to the delivery cost of the delivery unit determined based on the updated first sequence set and the updated second sequence set being less than a target delivery cost.

### Claim 6 (depends on 3)

The method according to claim 3, wherein after determining a delivery cost of the delivery unit based on the updated first sequence set and the updated second sequence set, the updating step further comprise:
counting a number of continuous determinations that the delivery cost of the delivery unit determined based on the updated first sequence set and the updated second sequence set is not less than the target delivery cost, in response to the delivery cost of the delivery unit determined based on the updated first sequence set and the updated second sequence set being not less than a target delivery cost;
selecting randomly an intermediate node, removing a destination node associated with the selected intermediate node comprised in the second sequence in the second sequence set to obtain a fourth sequence set, adding the removed destination node randomly to a fourth sequence in the fourth sequence set to generate the updated second sequence, updating the first sequence in the first sequence set based on the updated second sequence set, and determining the delivery cost of the delivery unit based on the updated first sequence set and the updated second sequence set, in response to the counted number being greater than a preset threshold; and
determining the delivery cost of the delivery unit determined based on the updated first sequence set and the updated second sequence set as the target delivery cost.

### Claim 7 (depends on 1)

The method according to claim 1, wherein the determining, based on the updated first sequence set and the updated second sequence set, a route of the to-be-delivered items delivered from the initial node to the destination node via the intermediate node, in response to the determined delivery cost meeting a preset delivery cost condition comprises:
acquiring a minimum delivery cost in the determined delivery cost in response to meeting a preset update termination condition; and
determining the route of the to-be-delivered items delivered from the initial node to the destination node via the intermediate node based on a first sequence set and a second sequence set associated with the acquired delivery cost.

### Claim 8

An apparatus for planning a route, the apparatus comprising:
at least one processor; and
a memory storing instructions, wherein the instructions when executed by the at least one processor, cause the at least one processor to perform operations, the operations comprising:
acquiring task information, the task information comprising a location of an initial node where to-be-delivered items are located, a location of a destination node of the to-be-delivered items, and a location of an intermediate node between the initial node and the destination node;
generating initial route information based on the task information, the initial route information comprising a first sequence set and a second sequence set, the first sequence set comprising at least one first sequence, the first sequence being used to indicate a route of a delivery unit delivering the to-be-delivered items from the initial node to one of the intermediate node, the second sequence set comprising at least one second sequence, and the second sequence being used to indicate a route of the delivery unit delivering the to-be-delivered items from the one of the intermediate node to the destination node of the to-be-delivered items;
performing an updating step comprising: updating the second sequence in the second sequence set based on a preset rule; updating the first sequence in the first sequence set based on the updated second sequence set; and determining a delivery cost of the delivery unit based on the updated first sequence set and the updated second sequence set; and
determining, based on the updated first sequence set and the updated second sequence set, a route of the to-be-delivered items delivered from the initial node to the destination node via the intermediate node, in response to the determined delivery cost meeting a preset delivery cost condition.

### Claim 9 (depends on 8)

The apparatus according to claim 8, wherein the generating initial route information based on the task information comprises:
generating the second sequence in the second sequence set based on the task information using a large-scale neighborhood search algorithm;
determining, based on the generated second sequence, item information of the to-be-delivered items to be stored by each intermediate node; and
generating the first sequence in the first sequence set based on the determined item information using the large-scale neighborhood search algorithm.

### Claim 10 (depends on 8)

The apparatus according to claim 8, wherein the updating the second sequence in the second sequence set based on a preset rule comprises:
removing randomly a predetermined number of the destination node comprised in the second sequence in the second sequence set to obtain a third sequence set, and add randomly the removed destination node to a third sequence in the third sequence set to generate the updated second sequence set.

### Claim 11 (depends on 8)

The apparatus according to claim 8, wherein the updating the first sequence in the first sequence set based on the updated second sequence set comprises:
determining, based on the updated second sequence set, item information of the to-be-delivered item to be stored by the intermediate node; and
generating the first sequence in the first sequence set based on the determined item information using a large-scale neighborhood search algorithm.

### Claim 12 (depends on 10)

The apparatus according to claim 10, wherein after determining a delivery cost of the delivery unit based on the updated first sequence set and the updated second sequence set, the updating step further comprise:
determining the delivery cost of the delivery unit determined based on the updated first sequence set and the updated second sequence set as the target delivery cost, in response to the delivery cost of the delivery unit determined based on the updated first sequence set and the updated second sequence set being less than a target delivery cost.

### Claim 13 (depends on 10)

The apparatus according to claim 10, wherein after determining a delivery cost of the delivery unit based on the updated first sequence set and the updated second sequence set, the updating step further comprise:
counting a number of continuous determinations that the delivery cost of the delivery unit determined based on the updated first sequence set and the updated second sequence set is not less than the target delivery cost, in response to the delivery cost of the delivery unit determined based on the updated first sequence set and the updated second sequence set being not less than a target delivery cost;
selecting randomly an intermediate node, removing a destination node associated with the selected intermediate node comprised in the second sequence in the second sequence set to obtain a fourth sequence set, adding the removed destination node randomly to a fourth sequence in the fourth sequence set to generate the updated second sequence, updating the first sequence in the first sequence set based on the updated second sequence set, and determining the delivery cost of the delivery unit based on the updated first sequence set and the updated second sequence set, in response to the counted number being greater than a preset threshold; and
determining the delivery cost of the delivery unit determined based on the updated first sequence set and the updated second sequence set as the target delivery cost.

### Claim 14 (depends on 8)

The apparatus according to claim 8, wherein the determining, based on the updated first sequence set and the updated second sequence set, a route of the to-be-delivered items delivered from the initial node to the destination node via the intermediate node, in response to the determined delivery cost meeting a preset delivery cost condition comprises:
acquiring a minimum delivery cost in the determined delivery cost in response to meeting a preset update termination condition; and
determining the route of the to-be-delivered items delivered from the initial node to the destination node via the intermediate node based on a first sequence set and a second sequence set associated with the acquired delivery cost.

### Claim 15

A non-transitory computer readable medium, storing a computer program thereon, the program, when executed by a processor, causes the processor to perform operations, the operations comprising:
acquiring task information, the task information comprising a location of an initial node where to-be-delivered items are located, a location of a destination node of the to-be-delivered items, and a location of an intermediate node between the initial node and the destination node;
generating initial route information based on the task information, the initial route information comprising a first sequence set and a second sequence set, the first sequence set comprising at least one first sequence, the first sequence being used to indicate a route of a delivery unit delivering the to-be-delivered items from the initial node to one of the intermediate node, the second sequence set comprising at least one second sequence, and the second sequence being used to indicate a route of the delivery unit delivering the to-be-delivered items from one of the intermediate node to the destination node of the to-be-delivered items;
performing an updating step comprising:
updating the second sequence in the second sequence set based on a preset rule; updating the first sequence in the first sequence set based on the updated second sequence set; and determining a delivery cost of the delivery unit based on the updated first sequence set and the updated second sequence set; and
determining, based on the updated first sequence set and the updated second sequence set, a route of the to-be-delivered items delivered from the initial node to the destination node via the intermediate node, in response to the determined delivery cost meeting a preset delivery cost condition.
