Search results for "assignment"
showing 10 items of 101 documents
Hybridizing the cross-entropy method: An application to the max-cut problem
2009
Cross-entropy has been recently proposed as a heuristic method for solving combinatorial optimization problems. We briefly review this methodology and then suggest a hybrid version with the goal of improving its performance. In the context of the well-known max-cut problem, we compare an implementation of the original cross-entropy method with our proposed version. The suggested changes are not particular to the max-cut problem and could be considered for future applications to other combinatorial optimization problems.
Applying fuzzy Particle Swarm Optimization to Multi-unit Double Auctions
2010
Abstract In the context of Quadratic Programming Problems, we use a fuzzy Particle Swarm Optimization (PSO) algorithm to analyze a Multi-unit Double Auction (MDA) market. We give also a Linear Programming (LP) based upper bound to help the decision maker in dealing with constraints in the mathematical model. In the computational study, we evaluate our algorithm and show that it is a feasible approach for processing bids and calculating assignments.
A Memetic Algorithm for Binary Image Reconstruction
2008
This paper deals with a memetic algorithm for the reconstruction of binary images, by using their projections along four directions. The algorithm generates by network flows a set of initial images according to two of the input projections and lets them evolve toward a solution that can be optimal or close to the optimum. Switch and compactness operators improve the quality of the reconstructed images which belong to a given generation, while the selection of the best image addresses the evolution to an optimal output.
A heuristic for fast convergence in interference-free channel assignment using D1EC coloring
2010
This work proposes an efficient method for solving the Distance-1 Edge Coloring problem (D1EC) for the assignment of orthogonal channels in wireless networks with changing topology. The coloring algorithm is performed by means of the simulated annealing method, a generalization of Monte Carlo methods for solving combinatorial problems. We show that the simulated annealing-based coloring converges fast to a suboptimal coloring scheme. Furthermore, a stateful implementation of the D1EC scheme is proposed, in which network coloring is executed upon topology changes. The stateful D1EC is also based on simulated annealing and reduces the algorithm’s convergence time by one order of magnitude in …
A New Approach to the Stock Location Assignment Problem by Multidimensional Scaling and Seriation
1999
The problem of the best stock location assignment in a warehouse has a fundamental role while optimising picking activities. In the present paper, this problem has been faced by considering seven variables to compute similarity between items. In this context, the problem of the choice of the most adequate similarity (or dissimilarity) measure between units while applying Multidimensional Scaling (MDS), has been examined. Besides the right metric, the possibility of applying a Seriation algorithm has been also considered. By using both MDS and seriation not just a single target can be considered, but we are able to manage with a plenty of variables; on the contrary with techniques used in li…
Time-Dependent Multiple Depot Vehicle Routing Problem on Megapolis Network under Wardrop's Traffic Flow Assignment
2018
In this work multiple depot vehicle routing problem is considered in case of variable travel times between nodes on a metropolis network. This variant of the classic multiple depot vehicle routing problem is motivated by the fact that in urban contexts variable traffic conditions play an essential role and can not be ignored in order to perform a realistic optimization. Time-travel matrices corresponding to each period of planning horizon were formed by solving the traffic assignment problem in conjunction with shortest path problem. Routing problem instances include from 20 to 100 customers randomly chosen from a road network of Saint-Petersburg. The results demonstrate that taking into ac…
Branch-and-Bound
2010
We now turn to the discussion of how to solve the linear ordering problem to (proven) optimality. In this chapter we start with the branch-and-bound method which is a general procedure for solving combinatorial optimization problems. In the subsequent chapters this approach will be realized in a special way leading to the so-called branch-and-cut method. There are further possibilities for solving the LOP exactly, e.g. by formulating it as dynamic program or as quadratic assignment problem, but these approaches did not lead to the implementation of practical algorithms and we will not elaborate on them here.
Nash Equilibrium in a Road Network with Many Groups of Users
2019
In this chapter concentrates on the relationships between individual and group behaviour of drivers in a road network. Such relationships are established by comparing the optimal routing of drivers (system optimum of Wardrop), the competitive drivers’ groups routing (Nash equilibrium), and the selfish drivers routing (user equilibrium of Wardrop). Thus, the boundary conditions for traffic assignment in a road network were recently obtained for the first time. Wide analytical discussion on the topic as well as a survey of relevant references are presented. Moreover, a new behavioural model of traffic assignment in case of simultaneous selfish and group behaviour of drivers in a road network …
Identification and potential origin of invasive clawed frogsXenopus(Anura: Pipidae) in Sicily based on mitochondrial and nuclear DNA
2013
African clawed frogs of the widespread polytypic species Xenopus laevis Daudin, 1802 (ranging large parts of sub-Saharan Africa) have been spreading since the 1940s, and have established reproductive populations in Europe, Asia and the Americas, where they can have negative impact as competitors of native amphibians and as disease vectors for chytridomycosis or ranaviruses. Here we use two mitochondrial (cytochrome b, 16S rDNA) and one nuclear (RAG 1: Recombination Associated Gene 1) DNA markers to infer the potential origin of invasive clawed frogs from Sicily that represent the largest invasive population in Europe. Identical mtDNA haplotypes match with those of Xenopus laevis, and Sicili…
Statistical Multivariate Techniques for the Stock Location Assignment Problem
1998
In previous papers we proposed to apply multivariate statistical methodologies, like Multidimensional Scaling (MDS) and Seriation to the stock location assignment problem of a warehouse, often solved by considering the Cube per Order Index (COI). In this paper we compare the results by MDS, Seriation, a COI based method and the Maximum Path criterion, considering the data of a whole year of a Sicilian supermarket chain warehouse. The comparison is based on the simulated times to satisfy a sample of real orders.