Heuristics for Two Depot Heterogeneous Unmanned Vehicle Path Planning to Minimize Maximum Travel Cost

Area of Science:

• Operations Research
• Robotics
• Logistics Optimization

Background:

• The multiple depot heterogeneous traveling salesman problem (MDHTSP) with a min-max objective is critical for reducing job completion times in applications like unmanned vehicle operations.
• Existing methods often struggle with the complexities of heterogeneous vehicle capabilities and distinct depot locations.

Purpose of the Study:

• To develop novel heuristics for the MDHTSP involving two structurally heterogeneous unmanned vehicles operating from different depots.
• To minimize the maximum travel cost, thereby reducing overall job completion time.

Main Methods:

• The study proposes two heuristics based on a primal-dual technique.
• These heuristics address task allocation and routing for two heterogeneous unmanned vehicles with differing travel costs.
• The methods are designed for both symmetric and asymmetric travel cost scenarios.

Main Results:

• The proposed algorithms generate feasible solutions for the MDHTSP.
• The solutions are of good quality, effectively minimizing the maximum travel cost.
• The heuristics achieve these results within relatively short computation times.

Conclusions:

• The developed heuristics offer an effective approach to solving the min-max MDHTSP for two heterogeneous unmanned vehicles.
• The methods provide a practical solution for optimizing task allocation and routing to reduce job completion times.
• This research contributes to efficient unmanned vehicle deployment in complex logistical scenarios.