ACO-Based Neighborhoods for Fixed-charge CapacitatedMulti-commodity Network Design Problem

The fixed-charge Capacitated Multi-commodity Network Design (CMND) is a well-known problemof both practical and theoretical significance. Network design models represent a wide varietyof planning and operation management issues in transportation telecommunication, logistics, productionand distribution. In this paper, Ant Colony Optimization (ACO) based neighborhoods areproposed for CMND problem. In the proposed neighborhoods, first, an open arc based on the incumbentsolution is closed; then, by using an ant colony optimization algorithm called Ant ColonySystem (ACS), a new solution is generated by constructing new paths for the demands deliveredon the closed arc. An algorithm is presented to construct new paths by using ACS algorithm fordemands with continuous volume. A sub mixed integer programming (MIP) model is then createdby joining the ACS and incumbent solutions. The generated sub-MIP is solved by using anMIP solver and its solution is considered as a neighborhood. In order to evaluate the proposedneighborhoods, an algorithm is developed. The algorithm parameters are tuned by using design ofexperiments. To assess the algorithm, several benchmark problems with different sizes are used.The statistical analysis shows the efficiency and effectiveness of the proposed algorithm comparedto the best approaches found in the literature

Keywords:

Ant Colony Optimization(ACO) , ACO-Based neighborhoods , Fixed-charge capacitatedmulti-commodity network design , meta-heuristic