Search

This paper investigates the clustered shortest-path tree (CluSPT) problem, a generalized network design problem that has several applications in various areas such as network design, agricultural irrigation settings, distribution of goods and products, etc. The main characteristic of the investigated problem is its hierarchical structure with the nodes of the underlying graph split into a given number of clusters. Its aim is finding a shortest-path spanning tree from a predefined source node to all the other nodes of the graph, with the property that every cluster should generate a connected subgraph. In this paper, we present two different two-level genetic algorithms (GAs) for solving the clustered shortest-path tree problem, in which, a framework with a macro-level sub-problem is used to generate trees spanning the clusters using two different Cayley encodings. The encodings in question are Prüfer and Dandelion codes. This sub-problem is coupled with a micro-level sub-problem that determines the best corresponding feasible solution of the CluSPT problem associated to a given tree spanning the clusters by means of a dynamic programming algorithm. Extensive computational results are stated and interpreted on the two sets of benchmark instances available from the literature and containing 452 non-euclidean instances. The achieved results prove that our novel two-level based genetic algorithms are highly competitive against the existing solution approaches from the specialized literature, more precisely, 146 best known solutions were equaled and new improved solutions were found for 292 out of 452 benchmark instances. Between our proposed solution approaches the differences are not remarkable for small instances, but when the size of the problem grows, the GA based on Dandelion code outperforms the GA based on Prüfer code, being better suited to evolutionary search due to its locality and heritability properties. • We focus on the clustered shortest-path tree (CluSPT) problem. • We present two different two-level genetic algorithms for solving the problem. • The problem is decomposed into two sub-problems that are solved separately. • The results prove that our algorithms are competitive against existing approaches. [ABSTRACT FROM AUTHOR]

This paper deals with a sustainable supply chain network design problem (SSCNDP) arising in the public sector. In the considered SSCNDP, given a manufacturer, a set of m potential distribution centers (DCs) having a given distinct capacity, and a set of n customers, each one with a particular demand, we have to select the number and the location of the DCs necessary to supply demands to all the customers and the allocation of the customers to these DCs such that the installation and transportation costs integrated with greenhouse gas (GHG) emissions are minimized. Due to the complexity of the problem, an efficient Reverse Distribution System (RDS) consisting of several improved classical heuristic algorithms is proposed. The developed approaches were tested and promising results were obtained on benchmark instances based on the literature, involving between 10 and 50 distribution centers and between 10 and 100 customers. [ABSTRACT FROM AUTHOR]

Abstract: In this paper, we describe a generalization of the multidimensional two-way number partitioning problem (MDTWNPP) where a set of vectors has to be partitioned into p sets (parts) such that the sums per every coordinate should be exactly or approximately equal. We will call this generalization the multidimensional multi-way number partitioning problem (MDMWNPP). Also, an efficient memetic algorithm (MA) heuristic is developed to solve the multidimensional multi-way number partitioning problem obtained by combining a genetic algorithm (GA) with a powerful local search (LS) procedure. The performances of our memetic algorithm have been compared with the existing numerical results obtained by CPLEX based on an integer linear programming formulation of the problem. The solution reveals that our proposed methodology performs very well in terms of both quality of the solutions obtained and the computational time compared with the previous method of solving the multidimensional two-way number partitioning problem. [Copyright &y& Elsevier]

Abstract: The generalized vehicle routing problem (GVRP) is an extension of the vehicle routing problem (VRP) and was introduced by Ghiani and Improta . The GVRP is the problem of designing optimal delivery or collection routes from a given depot to a number of predefined, mutually exclusive and exhaustive node-sets (clusters) which includes exactly one node from each cluster, subject to capacity restrictions. The aim of this paper is to provide two new models of the GVRP based on integer programming. The first model, called the node formulation is similar to the Kara–Bektaş formulation , but produces a stronger lower bound. The second one, called the flow formulation, is completely new. We show as well that under specific circumstances the proposed models of the GVRP reduces to the well known routing problems. Finally, the GVRP is extended for the case in which the vertices of any cluster of each tour are contiguous. This case is defined as the clustered generalized vehicle routing problem and both of the proposed formulations of GVRP are adapted to clustered case. [Copyright &y& Elsevier]