Overview

Multiple Traveling Salesman Problem (MTSP) Analysis, also known as Multiple Traveling Salesman Problem (TSP) Analysis, refers to the Network Dataset. Given M distribution centers and N MTSP stops (M, N are integers greater than zero), the most economical and efficient distribution path is found, and the corresponding transportation route is given. The Multiple Traveling Salesman Problem (MTSP) Analysis function provided by SuperMap GIS desktop is to solve the problem of how to assign the distribution order and delivery route of each truck. Minimize the total cost of distribution or the cost of each distribution center.

Application provides two delivery schemes: minimum total cost and global average optimization. By default, the scheme with the minimum total cost is used for distribution. It may happen that some MTSP Center Stop spend more on distribution while other MTSP Center Stop spend less, that is, the cost of different distribution centers is not balanced. The Overall Average Cost will control the cost of each MTSP Center Stop, so that the cost of each center point is relatively average, and the total cost is not necessarily the smallest.

Application example

There are three large-scale agricultural wholesale markets in a region, supplying vegetables and fruits to 13 community vegetable markets. Every day, the farmers'market dispatches three delivery trucks from their respective locations (MTSP Center Stop) to 13 community vegetable markets (MTSP Stop). Each truck needs to deliver goods to its own delivery point in the optimal order, and the total cost of the delivery route should be minimized. The Multiple Traveling Salesman Problem (MTSP) Analysis provided by SuperMap can help solve such problems.

The Analyst Result of Multiple Traveling Salesman Problem (MTSP) Analysis will display the optimal delivery path in Map intuitively, and generate an attribute table to record the node information and cost of each delivery arc. The Analyst Result is shown in the figure below. The red icon represents the MTSP Center Stop, the brown icon represents the MTSP Stop, and the routes in different colors represent different delivery routes.

Multiple Traveling Salesman Problem (MTSP) AnalysisAnalyst Result