Loop-wise route representation method for vehicle routing problem and the corresponding optimization formulation

A route optimization method for a vehicle routing problem, the route optimization method comprising:

• defining, by a loop variable designer, a loop as a set of links of a predetermined directionality including a clockwise direction or a counterclockwise direction in which a start node and an end node are the same in a graph including nodes and links to mathematically express the route;
• defining, by the loop variable designer, loop variables that are virtual variables each having a continuous value between a negative base route value and a positive base route value assigned in a predetermined directionality including a clockwise direction or a counterclockwise direction to the loop defined as the set of links;
• defining, by a base route designer, a base route that connects an origin node and a destination node of the route and has a positive value and of which a travel direction is set in a direction from the origin node to the destination node;
• and
• formulating, by an effective route searcher, an effective route problem using the loop variables and the base route.

A route optimization apparatus for a vehicle routing problem, the route optimization apparatus comprising:

• a loop variable designer configured to define a loop as a set of links of a predetermined directionality including a clockwise direction or a counterclockwise direction in which a start node and an end node are the same in a graph including nodes and links to mathematically express the route, and to define loop variables that are virtual variables each having a continuous value between a negative base route value and a positive base route value assigned in a predetermined directionality including a clockwise direction or a counterclockwise direction to the loop defined as the set of links;
• a base route designer configured to define a base route that connects an origin node and a destination node of the route and has a positive value and of which a travel direction is set in a direction from the origin node to the destination node;
• and
• an effective route searcher configured to formulate an effective route problem using the loop variables and the base route.