###### Abstract  
This article deals with the modified Multi-Depot Vehicle Routing Problem (MDVRP). The modification consists of altering the optimization criterion. The optimization criterion of the standard MDVRP is to minimize the total sum of routes of all vehicles, whereas the criterion of modified MDVRP (M-MDVRP) is to minimize the longest route of all vehicles, i.e., the time to conduct the routing operation is as short as possible. For this problem, a metaheuristic algorithm--based on the Ant Colony Optimization (ACO) theory and developed by the author for solving the classic MDVRP instances--has been modified and adapted for M-MDVRP. In this article, an additional deterministic optimization process which further enhances the original ACO algorithm has been proposed. For evaluation of results, [PERSON]'s benchmark instances are used. metaheuristic algorithm; ant colony optimization; multi-depot vehicle routing problem; time minimization; additional optimization process +
Footnote †: journal:  
pagel  
was introduced by [PERSON] et al. [6], who consider papers published between 1988 and 2014. Several variants of MDVRP are studied in the article: time windows, split delivery, heterogeneous fleet, periodic deliveries, and pickup and delivery. Another survey of publications on VRP and its variants can be found in [7], where 277 articles published between 2009 and 2015 are classified. Popular metaheuristic algorithms for MDVRP are based on the tabu search approach. One of the first tabu search-based algorithms was published by [PERSON] and [PERSON] in 1976 [8]. The same approach is used by [PERSON], [PERSON] and [PERSON] [9], or [PERSON], [PERSON] and [PERSON] [10], and indeed, examples of new algorithms using the tabu search approach continue to be published [11; 12]. Other popular metaheuristic approaches for MDVRP are simulated annealing [13; 14] and genetic algorithms [15]. A hybrid algorithm, based on both simulated annealing and the genetic approach, was proposed by [PERSON] et al. [16]. An excellent survey of papers using genetic algorithms for MDVRP can be found in [17]. More recently, bio-inspired algorithms have also been broadly used for MDVRP. Ant colony optimization algorithms are inspired by the behavior of ants when searching for food. There are many publications using this for MDVRP. [PERSON], [PERSON] and [PERSON] [18] proposed an algorithm which transfers the problem to VRP by inserting a virtual central depot (V-MDVRP). Another solution was proposed by [PERSON] et al. [19], who applied the ACO algorithm to a seafood product delivery routing problem. The most recent works include algorithms by [PERSON] [20], [PERSON] [21], and [PERSON] et al. [22]. In the last few years, hybrid metaheuristic methods have emerged. They combine features from various methodologies to take advantage of their different strengths. [PERSON] and [PERSON] [23] introduced a combination of the ant colony algorithm, and simulated annealing for MDVRP with time windows. [PERSON] et al. [24] proposed a method which combines the exploration breadth of population-based evolutionary searches, the aggressive-improvement capabilities of neighborhood-based metaheuristics, and advanced population-diversity management schemes. [PERSON] et al. [25] developed an approach called a \"cooperative coevolutionary algorithm\", inspired by the simultaneous evolution process involving two or more species. The MDVRP with a modified optimization criterion (known as Min-Max MDVRP) was first introduced by [PERSON] et al. in 2009 [2], who proposed a simple linear programming-based heuristic algorithm for solutions. Several papers have been published on this topic since then. [PERSON] et al. proposed an ant colony optimization algorithm both for Min-Max Single VRP and Multi-Depot VRP in 2013 [3]. In this paper, the authors compared results of their algorithm with those of the LP-based algorithm, proposed by [PERSON], on 11 scenarios.