Secondary traveling salesman problem solving method and system based on deep reinforcement learning

A traveling salesman problem and reinforcement learning technology, applied in the field of solving the secondary traveling salesman problem, can solve the problem that the secondary traveling salesman problem cannot be solved, and achieve the effect of avoiding the dependence on professional knowledge

Pending Publication Date: 2022-04-22
SUN YAT SEN UNIV
View PDF0 Cites 0 Cited by
  • Summary
  • Abstract
  • Description
  • Claims
  • Application Information

AI Technical Summary

Problems solved by technology

This scheme is suitable for the most primitive traveling salesman problem, and cannot be solved for the second traveling salesman problem

Method used

the structure of the environmentally friendly knitted fabric provided by the present invention; figure 2 Flow chart of the yarn wrapping machine for environmentally friendly knitted fabrics and storage devices; image 3 Is the parameter map of the yarn covering machine
View more

Image

Smart Image Click on the blue labels to locate them in the text.
Viewing Examples
Smart Image
  • Secondary traveling salesman problem solving method and system based on deep reinforcement learning
  • Secondary traveling salesman problem solving method and system based on deep reinforcement learning
  • Secondary traveling salesman problem solving method and system based on deep reinforcement learning

Examples

Experimental program
Comparison scheme
Effect test

Embodiment 1

[0055] This embodiment provides a method for solving the quadratic traveling salesman problem based on deep reinforcement learning, such as figure 1 shown, including the following steps:

[0056] S1: Define the quadratic traveling salesman problem, that is, in a vertex in a directed complete graph, the travel cost required to return to the starting point after visiting all the remaining point sets once and only once;

[0057] S2: Construct a deep reinforcement learning framework for solving the quadratic traveling salesman problem;

[0058] S3: Solving the quadratic traveling salesman problem through the deep reinforcement learning framework to obtain a sequence of access points.

[0059] The secondary traveling salesman problem in the step S1 is specifically:

[0060] In the directed complete graph G=(V, E), where V represents a point set, which contains n vertices to be visited; E represents an edge set, and the lengths of the opposite sides in the edge set E are equal in ...

Embodiment 2

[0087] This embodiment provides a specific embodiment of embodiment 1, specifically:

[0088] The angle-distance traveling salesman problem is tested in ten sets of data with instance sizes 30 and 40, respectively. For the angle-distance traveling salesman problem, we test in five sets of data with instance sizes 30 and 40, respectively. Table 1 shows the test results of the angle traveling salesman problem, and table 2 shows the test results of the angle-distance traveling salesman problem.

[0089] Optimal corresponds to the exact solution opt of each group of instance data, ours corresponds to the solution under the method of the present invention, gap is the gap between the present invention and the exact solution, the calculation formula is (ours-opt) / opt, and the penultimate line The average gap is the average gap of the solution of the method of the present invention, and the optimal gap is the gap between the optimal solution and the exact solution in the heuristic alg...

Embodiment 3

[0095] A quadratic traveling salesman problem solving system based on deep reinforcement learning, such as Figure 6 shown, including:

[0096] A problem module, the problem module defines a quadratic traveling salesman problem, that is, in a certain vertex in a directed complete graph, the travel cost required to return to the starting point after visiting all remaining point sets once and only once;

[0097]A deep reinforcement learning module, the depth reinforcement learning module constructs a deep reinforcement learning framework for solving the secondary traveling salesman problem;

[0098] A solving module, the solving module solves the quadratic traveling salesman problem through the deep reinforcement learning framework, and obtains a sequence of access points.

[0099] The same or similar reference numerals correspond to the same or similar components;

[0100] The terms describing the positional relationship in the drawings are only for illustrative purposes and ...

the structure of the environmentally friendly knitted fabric provided by the present invention; figure 2 Flow chart of the yarn wrapping machine for environmentally friendly knitted fabrics and storage devices; image 3 Is the parameter map of the yarn covering machine
Login to view more

PUM

No PUM Login to view more

Abstract

The invention discloses a secondary traveling salesman problem solving method and system based on deep reinforcement learning, and the method comprises the following steps: S1, defining a secondary traveling salesman problem, i.e., at a certain vertex in a directed complete graph, visiting all remaining point sets once and only once, and then returning to a starting point at required travel cost; s2, constructing a deep reinforcement learning framework for solving a secondary traveling salesman problem; and S3, solving the secondary traveling salesman problem through the deep reinforcement learning framework to obtain an access point sequence. According to the method, the approximate solution of the secondary traveling salesman problem can be obtained in an extremely short time, and the problems that an accurate solution method is too long in solving time, cannot calculate and respond in real time, and even cannot obtain an effective solution for the problem scale expansion are solved; and meanwhile, due to the fitting capability of the deep reinforcement learning framework model, the dependence of a heuristic algorithm on the construction of an iterative computation framework and the professional knowledge of a designer is avoided.

Description

technical field [0001] The present invention relates to the field of operations research / combinatorial optimization, and more specifically, to a method and system for solving a quadratic traveling salesman problem based on deep reinforcement learning. Background technique [0002] The traveling salesman problem is a very typical NP-Hard combinatorial optimization problem, and the quadratic traveling salesman problem derived from the traveling salesman problem is also a kind of NP-Hard problem. The difference from the traveling salesman problem is that the cost depends not only on each pair of two vertices traversed consecutively in a cycle, but also on each triplet of vertices traversed consecutively in a cycle. The secondary traveling salesman problem is mainly widely used in the scheduling management industry of logistics. According to different definitions of optimization goals in real life, it is divided into angle traveling salesman problem and angle-distance traveling ...

Claims

the structure of the environmentally friendly knitted fabric provided by the present invention; figure 2 Flow chart of the yarn wrapping machine for environmentally friendly knitted fabrics and storage devices; image 3 Is the parameter map of the yarn covering machine
Login to view more

Application Information

Patent Timeline
no application Login to view more
Patent Type & Authority Applications(China)
IPC IPC(8): G06Q10/04G06Q10/06G06Q50/28G06N3/04G06N3/08
CPCG06Q10/04G06Q10/0631G06Q50/28G06N3/04G06N3/08
Inventor 张航张子臻
Owner SUN YAT SEN UNIV
Who we serve
  • R&D Engineer
  • R&D Manager
  • IP Professional
Why Eureka
  • Industry Leading Data Capabilities
  • Powerful AI technology
  • Patent DNA Extraction
Social media
Try Eureka
PatSnap group products

Browse by: Latest US Patents, China's latest patents, Technical Efficacy Thesaurus, Application Domain, Technology Topic.

© 2024 PatSnap. All rights reserved.Legal|Privacy policy|Modern Slavery Act Transparency Statement|Sitemap