Search results for "Assignment problem"
showing 10 items of 30 documents
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 …
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.
Transportation Processes Modelling in Congested Road Networks
2019
In this chapter, the models of different transportation processes in a congested road network are considered. The first section is devoted to a signal control problem formulated as a bi-level optimization program. An analytical solution for a two-commodity linear road network offers a practical and illustrative result to be taken into consideration by decision-makers in this sphere. A new algorithm for OD-matrix estimation based on the dual traffic assignment problem is described in the second section. The third section is devoted to the problem of emission reduction. The approaches presented in this book are shown to be well-implemented for coping with such problems. The time-depended vehi…
Multidimensional scaling and stock location assignment in a warehouse: an application
1999
By means of an application, in the present paper, the suitability of a multivariate statistical methodology, as multidimensional scaling (MDS), to solve an optimization problem is shown. In particular, considering the stock location assignment problem in the warehouse of a supermarket chain, the solution gained by applying MDS to a set of seven variables is compared with the one obtainable by considering the usual techniques applied in this context. A wide discussion of results is reported. Copyright © 1999 John Wiley & Sons, Ltd.
A combined interval-valued ELECTRE TRI and TOPSIS approach for solving the storage location assignment problem
2019
Abstract Efficiency and effectiveness of logistic activities, in general, and of distribution networks, in particular, are largely influenced by the way warehouses operate as nodes of these networks. In recent years, warehouse management has undergone major changes due to the increase of e-commerce and competition in time-reduction. Despite that, logistic costs of warehouse processes (e.g. receiving, storage, order picking and shipping, etc.) are still often high. Referring to the order picking process, related activities may be optimized by a proper assignment of products to storage locations. In the literature, this problem is known as Storage Location Assignment Problem (SLAP). Due to th…
The combined distribution/assignment problem in transportation network planning: a parallel approach on hypercube architecture
1995
The joint distribution/assignment problem plays a central role in urban transport network planning. In this problem, according to the mathematical model proposed by S. P. Evans, the trips are iteratively calculated and assigned to the network in such a way that the resulting traffic flows pattern satisfies the selfish equilibrium condition. Unfortunately the number of variables and constraints increase hardly with the greatness of the networks causing long computational time for the equilibrium solution. In this paper an nCUBE 2 parallel computing architecture is employed to solve the combined problem and to asses the potential of MIMD machines to handle large scale transportation network p…
Cotas inferiores para el QAP-Arbol
1985
The Tree-QAP is a special case of the Quadratic Assignment Problem where the flows not equal zero form a tree. No condition is required for the distance matrix. In this paper we present an integer programming formulation for the Tree-QAP. We use this formulation to construct four Lagrangean relaxations that produce several lower bounds for this problem. To solve one of the relaxed problems we present a Dynamic Programming algorithm which is a generalization of the algorithm of this type that gives a lower bound for the Travelling Salesman Problem. A comparison is given between the lower bounds obtained by each ralaxation for examples with size from 12 to 25.
On enhancing the object migration automaton using the Pursuit paradigm
2017
Abstract One of the most difficult problems that is all-pervasive in computing is that of partitioning. It has applications in the partitioning of databases into relations, the realization of the relations themselves into sub-relations based on the partitioning of the attributes, the assignment of processes to processors, graph partitioning, and the task assignment problem, etc. The problem is known to be NP-hard. The benchmark solution for this for the Equi-Partitioning Problem (EPP) has involved the classic field of Learning Automata (LA), and the corresponding algorithm, the Object Migrating Automata (OMA) has been used in all of these application domains. While the OMA is a fixed struct…
A graph colouring model for assigning a heterogeneous workforce to a given schedule
1996
Abstract We analyze a heterogeneous workforce assignment problem in which the minimum number of workers required to carry out a machine load plan is calculated. The problem is formulated as a restricted vertex colouring problem and a branch and bound algorithm is presented. The special characteristics of the graph to be coloured allow an efficient implementation of the branch and bound. Computational results show that the algorithm can solve problems of 50 activities, 5, 10 and 15 machines and between 2 to 15 different types of workers in just a few seconds.