Permutation-Matrix Approach to Optimal Linear Assignment Design

Abstract

The paper presents a new iterative approach to solving Linear Assignment problems (LAP) and finding a perfect matching in a weighted bipartite graph iteratively. For that, a new permutation-matrix model of optimal linear assignment is proposed, which allows recursively finding solutions on a set of augmenting paths built based on the current matching. The results can be combined with other methods for solving a LAP such as the Hungarian Algorithm and minimal cost method in order to find an optimum faster. Linear Assignment Problem; optimal assignment; matching; augmenting path; routes;

1. Introduction

Transport Logistics is a broad application domain for Decision Theory and Optimization Theory dealing with routings and scheduling. It is inevitably connected with optimal placement in space and time of discrete objects. Therefore, Combinatorial Optimization is utilized widely in Transport

Logistics problems.

Among transport logistics problems are numerous models of optimizing closed routes (routing models), which contain some conditions and constraints inherent in the actual process of moving objects on a plane or in space. Therefore, routing problems are crucial in rational, from economic prospective to decision-making and accelerating transport operations and management.

Even the most complex routing problems have a lot in common with the classical Vehicle Routing Problem (VRP) formulated by Danzig and Ramser [ 1, 2 ] and extended in many sources [ 3, 4, 5, 6 ].

This paper is dedicated to a solution of one type of assignment problem (Linear Assignment Problem, LAP), which is, in turn, is closely related to the Salesman Problem (SP) of a formation of a close route of a minimum length in a graph. The SP is a classical NP-complete problem, while a LAP represents a narrow subclass of combinatorial optimization problems solvable for polynomial time. That is why it is highly perspective to find other approaches to a polynomial solution of a LAP and utilize it in effective metaheuristics for the SP.

2. Related work

Conventional methods for solving the Linear Assignment Problem, such as the Hungarian algorithm, Kahn-Munkres method, and potential method are based on different combinatorial

2020 Copyright for this paper by its authors. optimization approaches. They are all polynomial and characterized by different time complexity, while the best one is O n3 , where n is an order of their cost matrices [ 7, 8, 9, 10 ].

In [ 11 ], an algorithm for solving one version of the LAP is presented, which complexity has been reduced to O n2 . It was shown that the algorithm plays a role of procedure functions that can be embedded into the Branch and Bound method for solving LAPs. It resulted in faster than before calculating tighter lower bounds on the cost of closed routes in TSP.

This algorithm is designed to find a perfect matching of the minimum total weight in a weighted bipartite graph on 2n vertices. It utilizes an introduced concept of the shortest augmenting path in a graph [ 11, 12 ].

One of the common TSP settings is that the distances dij between each pair of cities i and j i, j  {1,  2,  , n} are known, and it is required to find such a sequence of the cities  [ 1 ],  [ 2 ],  ,  [i], ,   [n] minimizing the value n–1  d i i1  d n [ 1 ]  . i1 (1)

This value is equal to the length of the shortest route (bypass), starting in a city  [ 1 ] , passing through all cities in turn and ending in  [ 1 ] after visiting  [n]. The TSP, in which dij  d ji for each pair i, j of cities is called symmetric (STSP) [ 13, 14, 15 ].

TSP and STSP are strongly NP-complete problems. They belong to a class of combinatorial optimization problems and, reflecting a continuously growing set of applications and generalizations, remains a topical research topic [ 15, 16, 17, 18 ].

Suppose that, to each edge, it is assigned zero weight in a complete graph on n  1vertices (thus reflecting that all delivery routes are of the same cost), but there is a fee for using each vehicle unit. This fee is fixed for all vehicles of the same capacity. Here the task is to find the minimum number of cars that will transport n cargo diii .

This problem, known as the container packing problem, is NP-complete in the strong sense. Since VRP includes the TSP and packing problem conditions, there is unlikely to solve the VRP exactly by n efficient algorithms [ 15 ]. Besides, fulfilling a constraint i1dii   K  S for a given K  2 and a container capacity S is not a sufficient condition for the existence of a feasible VRP solution.

The VPR is representable as a TSP with constraints. Among the conditions is the one that there is a vehicle initially located in the depot. The vehicle must deliver a homogeneous cargo from production points to consumption ones and then return to the depot. The total number of points of production and consumption is n; they form a set N  {1,  2,  ,  n} , while the depo (the base) is assigned an index 0. The cost of transporting cargo from point i to point j ( i, j  {0}  N ), the vehicle capacity is equal to S , the weight qi of the load that must be delivered back from the point of production if qi  0 or n delivered to the point of consumption in case of qi  0 . Also, the balance condition i1qi  0 has to satisfy.

It is required to find a permutation  [ 1 ],  [ 2 ],  ,   [i], ,   [n] on set N such that u 0  q [i]   S,  u  N, 

i1 n–1 d0, 1   d i i1  d n,0   min i1 (2) (3)

It follows from expressions (1) and (3) that the formulated problem is the classical TSP, in which the set of feasible solutions satisfying condition (2) may be empty. For example, it has no solution 0,  [ 1 ],  [ 2 ],  ,   [i], ,   [n],  0 for S = 1, n = 5, qi  2 / 3 for suppliers i  1, 2, 3 and qi  –1 for consumers i  4, 5 [ 1 ].

Step one

di1 j1  mindi1 j1 , di1 j2 ,  di2 j1 ,  di2 j2 .

After solving the TSP with the matrix dij ij , one must return to the original transport network and add all the arcs to the resulting bypass.

For the VRP, several applied versions are known in the literature. These include, for example, the School Bus Routing Problem (SBRP), which has the following formulation. A school has a fleet of identical vehicles of capacity S, designed to deliver each student i to his residence after classes. The school has order number 0. The travel time tij from point i to point j is known, i, j 0  N , and the cost of the travel dij is known as well. Also, there is a requirement that each vehicle must return to point 0 no late than at time T [ 1 ].

In SBRP, it is required to find Boolean variables xij , i, j 0  N, and such a number K of the vehicles satisfying the following constraints: the point 0 is the beginning and end of a route of each vehicle, any delivery point i is included in a single route: n n xi0  x0i   k , i1 i1 n n xij  x ji 1 ;  j  N;  i1 i1 (4) (5) (6) (7) (8) (9) there are no routes that include only delivery points: the route 0,  i[ 1 ], i[ 2 ],  ,  i[ j], ,  i[r],  0, i[ j] N of the vehicle satisfies a capacity condition:

Also, there is a time limit T for the route execution:

The SBRP objective function is:

 xij  U ;   i, jU 

U   N  –1  x i[ j], i[ j 1 ]    –1   S  –1  . j1

r –1 t0i[ 1 ]  ti[ j], i[ j 1 ]  ti[ ]0   T. 

j1 n  dij xij   min.

i, j0

It is easy to see that, in the SBRP dii 1, i 1, n instead of dii  Z  in the VRP, and the number of vehicles is K  n / S  .

If, in the SBRP, the cost dij and time tij of moving the vehicle from a point i to a point j are linearly dependent, and dij  0 if tij  0 . (9) can be replaced by an objective function n  tij xij   min i, j 0 (10) (11) utilizing the initial data dij , i, j  {0}  N as auxiliary data for the economic assessment of the constructed solution.

The requirement dii 1 for i 1, n makes a search of (9) much easier. The constraint on the vehicle load takes the form of inequality k   n / S  . The latter is a necessary and sufficient condition for a feasible solution to the problem.

If we substitute r  n in (7) and (8), the SBRP becomes the TSP on a set of vertices 0  N,  N   n of a transport network represented by the full graph.

The k-VRP problem is closely related to the VRP. In contrast to the VRP, the k-VRP does not specify the amount dii of cargo delivered to the i-th consumer ( i 1, n ) and the capacity S of each vehicle, but it is required to serve at most k clients. It is necessary to minimize the total cost of routes of all vehicles, the number of which is equal to m  n / k . Therefore, the k-VRP is solvable for n, k   Z 

and n  k. For n  k , it is the TSP defined on a set of permutations induced by 0,  i1, i2,  ,  i j, ,  in, 0 . In particular, for k = 2, it is polynomially solvable, while for k   3 , it belongs to the class of NP-complete problems [ 15, 16, 19, 20, 21 ].

A peculiarity common for all the above routing problems is that they are formulated as generalizations or variants of the NP-complete problem TSP, where additional constraints are added. These constraints naturally make narrower the TSP feasible domain. The constraints lead to the problems' potential infeasibility, stimulating constant interest in further studying combinatorial optimization problems related to the TSP. In this paper, a new mathematical model of optimal assignment is described, which develops the results of [ 11, 12, 22, 23, 24, 25 ].

The paper goal is to build a permutation-matrix model of optimal assignment, which allows recursively finding solutions on a set of augmenting paths built from the current matching.

3. Main part

Let us describe the method for solving the LAP. We will use the following its formulation.For the matrix of costs (weights) C  cij ij of order n , where cij  R1 or cij  , where R0 is a set of non-negative real numbers, find

n C    min  ci, [i].

 Sn i1

Here    [ 1 ],  [ 2 ], ...,  [n] is a permutation of a set {1, 2, , n} of the columns’  indexes of the matrix C, Sn is the permutation group, and    [ 1 ],  [ 2 ], ...,  [n] is the optimal permutation (an optimum) corresponding to the objective function value C    in1ci [i] .

The LAP is feasible if

C     . Respectively, c [i]  , i  1, n . Note that a LAP with a cost matrix containing elements cij   may be unfeasible. In this case, it is necessary to establish that the feasible domain of the problem is empty.

Further, we will assume that we deal with a feasible LAP.

The permutation    [ 1 ], [ 2 ], ...,  [n], where C     , respectively, c [i]   i  1, n, is called a feasible solution to the LAP.

The core of the Hungarian algorithm for LAPs is that the cost matrix is equivalently transformed first to make a significant number of its elements zero. The one applies a greedy search to find as many as possible independent zeros. After that, directly the algorithm is applied, increasing by exactly one the set of independent zeros. Like the Hungarian algorithm, our approach to finding the permutation  sequentially increases by one on each iteration the number elements k, k  1, n, of the sequence representing a certain part of a feasible solution (a partial solution) of a LAP.

Let us list some properties of this sequence and outline the way of its construction.

Any part of a feasible solution of a LAP consisting of k elements determines uniquely a submatrix cis jt s,t of the matrix C having the order k , such that

i1  i2  ...  is  ...  ik , j1  j2  ...  jt  ...  jk .

Introduce a sequence

 k   k [i1],  k [i2 ], ...,  k [is ], ...,  k [ik ],  k [is ] j1, j2, ..., jt , ..., jk , k 1, n 1, such that: a) it is a solution TO the LAP having the submatrix cis jt s,t as its cost matrix; b) the cost of the assignment induced by the permutation  k does not exceed the optimal value of a LAP induced by any submatrix of C having the order k .

Let us try to develop a conversion procedure of a sequence  k into a sequence  k 1 . If such an efficient procedure exists for k  0, n 1 and the LAP (11) is feasible, then it takes n steps to find   n . Let us find out how the sequences  k , k  1, n may be constructed.

Step 1. The initial sequence 1  1[i1] is trivially defined and is identical to the minimal cost greedy method to solve LAPs. We derive the minimum value of the matrix and make the corresponding initial assignment of the order 1: let clr  mincij |1 i, j  n, respectively, i1  l,1  1[i1],1[i1]  r.

Step 2. In order to find  2   2[i1],  2[i2 ] from 1 , let us determine cms  mincij | i  l, j  r, clp  minclj | j  r, cvr  mincir | i  l (see Fig. 1). m l v w

p cmp clp q cwq r clr cvr

s cms cvs

It is easy to see that if clr  cms  clp  cvr (further Case 2.1), then conditions a) and b) are satisfied for a sequence  2 with i1  l,  2[i1]  r, i2  m,  2[i2 ]  s.

It corresponds to a submatrix of the matrix shown in Fig. 1 depicted in Fig. 2.

r s l clr cms r cvr

Step 3. Now, we transform the sequence  2 into a sequence  3   3[i1],  3[i2],  3[i3].

If we deal with Case 2.1, then next we find cwq  mincij | i  l, m; j  s, r (see Fig. 1) and the value

MIN1  clr  cms  cwq .

Note that cwq  cms , if  2   2[l]  p,  2[v]  r  , i.e. we deal with Case 2.2. The transformation from  2 into  3 is the result of solving the following auxiliary problem. For rows l, m and columns r, s of the matrix C induced by the elements first two least elements clr and cms , it is required to find a triple of components with the minimum sum of their values. Any two triple elements must be placed in three different rows, particularly including l, m and three various columns including r, s ones.

If such a triple does not contain clr , but includes cms , then the sum of its elements is bounded from below by the value

S1  cvr  clp  cms , where cvr  mincir | i  l, m, clp  minclj | j  r, s (further, Case 3.1).

Let the solution of the auxiliary problem be a triple, which includes clr and does not contain cms .

Then a value

S2  clr  cmp  cvs , where cmp  mincmj | j  s, r, cvs  mincis | i  l, m (further, Case 3.2).

Elements of a solution of the auxiliary problem that does not contain clr and cms define a value

S3  minclp  cmr  cws , cmq  cls  cvr  (further,

Case 3.3).

Here, cws  mincis | i  l, m, cls  mincis | i  m, v, cmq  mincmj | j  r, s (see Fig. 5).

Let cmr  mincmj | j  p, s (see

Fig. 4), MIN 2  minS1, S2 , S3.  3   3[l]  r,  3[m]  s,  3[w]  q (further, Case 3.4).

m l v w m l v w p

q cmq p

q cmq r clr cvr r clr cvr

s cms cls

s cms cls S3 given cws  mincis | i  l, m, cmr  mincmj | j  p, s S3 given cls  mincis | i  m, v, cmq  mincmj | j  r, s

Depending on which one of the Cases 3.1-3.4 corresponds to minMIN 2, MIN 2 , the sequence  3 is set.

Step k. A sequence  k   k [i1],  k [i2 ], ...,  k [is ], ...,  k [ik ] with the properties a) and b) generally is transformed into a sequence  k 1   k 1[i1],  k 1[i2], ...,  k 1[ir ], ...,  k 1[ik 1] with the same properties as the following.

In the matrix C , it is found

cik1, k [ik1]  mincij | i  i1, i2, ..., is , ..., ik , j   k [i1],  k [i2 ], ...,  k [is ], ...,  k [ik ], 1 then a sequence  k 1   k ,  k [ik 1] (further, Case k.1) is formed and

k MIN1   cis , k [is ]  cik 1, k [ik 1]

s1 is evaluated.

Next, the problem of finding k  1 elements is solved, for which in the matrix C the minimum sum of their values is attained. At the same time, they are located in different rows and columns, including all rows and columns with numbers specified by values c k [i2 ], ..., c k [is ], ..., c k [ik ]. This induces several cases Cases k.2-k.K and the values S2 ,..., SK . Then MIN 2  minS2,..., SK  is evaluated, and the partial permutation  k21 of the order k , where the value is achieved, is derived. Finally,  k 1 is found by assigning  k 1   1k 1 in case of c k [i1], MIN1  MIN 2 . Otherwise,  k 1   k21.

In the same way, the iterative process continues until  n will be found. Process terminates and   n is set.

The complexity of our method for solving LAPs described above has complexity O n3 , the best known so far and coinciding with the improved version of the Hungarian algorithm. This means that these two can be combined in order to get a hybrid method working, n average, better than the methods itself.

4. Conclusion

A new permutation-matrix model of optimal assignment is proposed. It allows recursively finding solutions on a set of augmenting paths built with respect to the current matching. The proposed scheme for finding an optimal assignment underlies a method of solving a LAP where a solution to the problem is found exclusively employing matching theory for bipartite graphs.

The developed model for finding the optimal destination develops transport logistics’  theory. It is focused on improving the organization of transportation in real-time and in real situations of vehicle traffic. Its implementation allows reducing the time and fuel consumption for carrying out transport works.

The method uses the well-known algorithm for finding maximum matchings in bipartite unweighted graphs, built according to a scheme that expands approaches to solving hard optimization problems.

5. References

References

[1] D. P. Bertsekas , Network Optimization: Continuous and Discrete Models , Athena Scientific, Belmont, Mass, 1998 .

[2] E.M. Bronshtein , T.A. Zaiko , Deterministic optimization problems of transport logistics, Automation and telemechanics, 10 (20100 113 - 147 .

[3] G. Cornuejols , F. Harche , Polyhedral study of the capacitated vehicle routing problem , Mathematical Programming , V. 60 , 1 - 3 ( 1993 ) 21 - 52 . doi: 10 .1007/BF01580599.

[4] A. Langevin , D. Riopel (Ed.), Logistics Systems: Design and Optimization , Springer US , 2005 . doi: 10 .1007/b106452.

[5] J.-Y. Potvin , Vehicle Routing, in: C. A. Floudas and P. M. Pardalos (Ed.), Encyclopedia of Optimization , Springer US, 2008 , pp. 4019 - 4022 . doi: 10 .1007/978-0- 387 -74759-0_ 702 .

[6] A. V. Vural , B. Eksioglu , Vehicle routing problem with simultaneous pickups and deliveries Vehicle Routing Problem with Simultaneous Pickups and Deliveries , in: C. A. Floudas and P. M. Pardalos (Ed.), Encyclopedia of Optimization , Springer US, 2008 , pp. 4022 - 4027 . doi: 10 .1007/978-0- 387 -74759-0_ 703 .

[7] D.J. Little , K. Murty , D. Sweeney , K. Carell , Algorithm for solving the travelling salesman problem, Economics and Mathematical Methods , V. 1 , 1 ( 1965 ) 90 - 107 .

[8] C. Helmberg , The m-Cost ATSP , in: G. Cornuéjols, R. E. Burkard and G. J. Woeginger (Ed.), Integer Programming and Combinatorial Optimization , Springer, Berlin, Heidelberg, 1999 , pp. 242 - 258 . doi: 10 .1007/3-540-48777-8_ 19 .

[9] E. Mainika , Optimization algorithms on networks and graphs , Mir, Moscow, 1981 .

[10] R. E. Burkard , E. Çela, Linear Assignment Problems and Extensions , in: D.- Z. Du and P. M. Pardalos (Ed.), Handbook of Combinatorial Optimization , Springer US , 1999 , pp. 75 - 149 . doi: 10 .1007/978-1- 4757 -3023- 4 _ 2 .

[11] A.V. Panishev , D.D. Plechisty , V.A. Shevchenko , Local search procedures in combinatorial algorithms for solving the general traveling salesman problem , Artificial Intelligence , 1 ( 2005 ) 465 - 470 .

[12] O.B. Matsiy , A.V. Morozov , A.V. Panishev, The Recurrent Method to Solve the Assignment Problem . Cybern Syst Anal , 51 , 2015 , pp. 939 - 946 . doi: 10 .1007/s10559-015-9786-x.

[13] S.M. Rezer , S.E. Lovetsky , I.I. Melamed , Mathematical methods of optimal planning in transport systems , Results of Science  and  Technology,  series  ”Organization  of  Transport  Management”,  1990 .

[14] E. X. Gimadi , A.V. Shahshneider , Approximate estimation algorithms for routing tasks at random inputs with a limited number of clients in each route , Automation and telemechanics , 2 ( 2012 ) 126 - 139 .

[15] C. H. Papadimitriou , K. Steiglitz , Combinatorial Optimization: Algorithms and Complexity . Dover Publications, Mineola, N.Y. , 1998 .

[16] M. R. Garey , D. S. Johnson , Computers and Intractability: A Guide to the Theory of NP-completeness , W.H. Freeman & Co Ltd , New York, 1979 .

[17] L. Lovasz , M. D. Plummer , Matching Theory, Chelsea Pub Co., Providence, R.I , 2009 .

[18] T.L. Saaty , Optimization in integers and related extremal problems: from a course given at the University of California, Los Angeles, and George Washington University, Washington DC, RWS Publications, 2014 .

[19] J. Evans , Optimization Algorithms for Networks and Graphs , 2nd ed., CRC Press, 2017 .

[20] K. Thulasiraman , S. Arumugam , A. Brandstädt , T. Nishizeki, Handbook of Graph Theory, Combinatorial Optimization , and Algorithms , CRC Press, 2016 .

[21] A. Langevin and D. Riopel (Eds.), Logistics Systems: Design and Optimization , Springer US , 2005 . doi: 10 .1007/b106452.

[22] O. Pichugina and O. Matsyi , Boolean Satisfiability Problem: Discrete and Continuous Reformulations with Applications , in Proceedings of the 2020 IEEE 15th International Conference on Advanced Trends in Radioelectronics , Telecommunications and Computer Engineering (TCSET), 2020 , pp. 623 - 627 . doi: 10 .1109/TCSET49122. 2020 . 235507 .

[23] Y.G. Stoyan , S.V. Yakovlev , Theory and Methods of Euclidean Combinatorial Optimization: Current Status and Prospects . Cybern Syst Anal , 56 ( 2020 ) 366 - 379 . https://doi.org/10.1007/s10559-020-00253-6.

[24] S. Yakovlev , O. Pichugina , On constrained optimization of polynomials on permutation set CEUR Workshop Proceedings , v. 2353 , 2019 , рр.  570 - 580 .

[25] I. Averbakh , W. Yu, Multi-depot traveling salesmen location problems on networks with special structure , Ann Oper Res, V. 286 , 1 ( 2020 ) 635 - 648 . doi: 10 .1007/s10479-018-2812-4.