assignment problem algorithm in daa

Index     Assignment problem     Hungarian algorithm     Solve online    

The assignment problem

The assignment problem deals with assigning machines to tasks, workers to jobs, soccer players to positions, and so on. The goal is to determine the optimum assignment that, for example, minimizes the total cost or maximizes the team effectiveness. The assignment problem is a fundamental problem in the area of combinatorial optimization.

Assume for example that we have four jobs that need to be executed by four workers. Because each worker has different skills, the time required to perform a job depends on the worker who is assigned to it.

The matrix below shows the time required (in minutes) for each combination of a worker and a job. The jobs are denoted by J1, J2, J3, and J4, the workers by W1, W2, W3, and W4.

Each worker should perform exactly one job and the objective is to minimize the total time required to perform all jobs.

It turns out to be optimal to assign worker 1 to job 3, worker 2 to job 2, worker 3 to job 1 and worker 4 to job 4. The total time required is then 69 + 37 + 11 + 23 = 140 minutes. All other assignments lead to a larger amount of time required.

The Hungarian algorithm can be used to find this optimal assignment. The steps of the Hungarian algorithm can be found here , and an explanation of the Hungarian algorithm based on the example above can be found here .

HungarianAlgorithm.com © 2013-2024

Branch and Bound Algorithm

Last updated: March 18, 2024

Baeldung Pro comes with both absolutely No-Ads as well as finally with Dark Mode , for a clean learning experience:

>> Explore a clean Baeldung

Once the early-adopter seats are all used, the price will go up and stay at $33/year.

1. Overview

In computer science, there is a large number of optimization problems which has a finite but extensive number of feasible solutions. Among these, some problems like finding the shortest path in a graph  or  Minimum Spanning Tree  can be solved in polynomial time .

A significant number of optimization problems like production planning , crew scheduling can’t be solved in polynomial time, and they belong to the NP-Hard class . These problems are the example of NP-Hard combinatorial optimization problem .

Branch and bound (B&B) is an algorithm paradigm widely used for solving such problems.

In this tutorial, we’ll discuss the branch and bound method in detail.

2. Basic Idea

Branch and bound algorithms are used to find the optimal solution for combinatory, discrete, and general mathematical optimization problems. In general, given an NP-Hard problem, a branch and bound algorithm explores the entire search space of possible solutions and provides an optimal solution.

A branch and bound algorithm consist of stepwise enumeration of possible candidate solutions by exploring the entire search space. With all the possible solutions, we first build a rooted decision tree. The root node represents the entire search space:

Here, each child node is a partial solution and part of the solution set. Before constructing the rooted decision tree, we set an upper and lower bound for a given problem based on the optimal solution. At each level, we need to make a decision about which node to include in the solution set. At each level, we explore the node with the best bound. In this way, we can find the best and optimal solution fast.

Now it is crucial to find a good upper and lower bound in such cases. We can find an upper bound by using any local optimization method or by picking any point in the search space. On the other hand, we can obtain a lower bound from convex relaxation  or  duality .

In general, we want to partition the solution set into smaller subsets of solution. Then we construct a rooted decision tree, and finally, we choose the best possible subset (node) at each level to find the best possible solution set.

3. When Branch and Bound Is a Good Choice?

We already mentioned some problems where a branch and bound can be an efficient choice over the other algorithms. In this section, we’ll list all such cases where a branch and bound algorithm is a good choice.

If the given problem is a discrete optimization problem, a branch and bound is a good choice. Discrete optimization is a subsection of optimization where the variables in the problem should belong to the discrete set. Examples of such problems are 0-1 Integer Programming  or  Network Flow problem .

Branch and bound work efficiently on the combinatory optimization problems. Given an objective function for an optimization problem, combinatory optimization is a process to find the maxima or minima for the objective function. The domain of the objective function should be discrete and large. Boolean Satisfiability , Integer Linear Programming are examples of the combinatory optimization problems.

4. Branch and Bound Algorithm Example

In this section, we’ll discuss how the job assignment problem can be solved using a branch and bound algorithm.

4.1. Problem Statement

We can assign any of the available jobs to any worker with the condition that if a job is assigned to a worker, the other workers can’t take that particular job. We should also notice that each job has some cost associated with it, and it differs from one worker to another.

Here the main aim is to complete all the jobs by assigning one job to each worker in such a way that the sum of the cost of all the jobs should be minimized.

4.2. Branch and Bound Algorithm Pseudocode

Now let’s discuss how to solve the job assignment problem using a branch and bound algorithm.

Let’s see the pseudocode first:

In the search space tree, each node contains some information, such as cost, a total number of jobs, as well as a total number of workers.

Now let’s run the algorithm on the sample example we’ve created:

4. Advantages

In a branch and bound algorithm, we don’t explore all the nodes in the tree. That’s why the time complexity of the branch and bound algorithm is less when compared with other algorithms.

If the problem is not large and if we can do the branching in a reasonable amount of time, it finds an optimal solution for a given problem.

The branch and bound algorithm find a minimal path to reach the optimal solution for a given problem. It doesn’t repeat nodes while exploring the tree.

5. Disadvantages

The branch and bound algorithm are time-consuming. Depending on the size of the given problem, the number of nodes in the tree can be too large in the worst case.

Also, parallelization is extremely difficult in the branch and bound algorithm.

6. Conclusion

One of the most popular algorithms used in the optimization problem is the branch and bound algorithm. We’ve discussed it thoroughly in this tutorial.

We’ve explained when a branch and bound algorithm would be the right choice for a user to use. Furthermore, we’ve presented a branch and bound based algorithm for solving the job assignment problem.

Finally, we mentioned some advantages and disadvantages of the branch and bound algorithm.

Hold on, while it loads...

Mastering LC Branch and Bound in DAA: A Comprehensive Guide

Learn how to solve complex optimization problems using the LC Branch and Bound algorithm in Design and Analysis of Algorithms (DAA). This in-depth guide covers the basics, implementation, and applications of this powerful technique.

Create an image featuring JavaScript code snippets and interview-related icons or graphics. Use a color scheme of yellows and blues. Include the title '7 Essential JavaScript Interview Questions for Freshers'.

LC Branch and Bound in DAA: A Comprehensive Guide

Introduction.

In the realm of Design and Analysis of Algorithms (DAA), the LC Branch and Bound method is a powerful technique used to solve complex optimization problems. This method is particularly useful in solving NP-hard problems, which are notoriously difficult to solve using traditional methods. In this blog post, we will delve into the world of LC Branch and Bound, exploring its principles, advantages, and applications.

What is LC Branch and Bound?

The LC Branch and Bound method is a hybrid algorithm that combines the strengths of two popular optimization techniques: Linear Programming (LP) and Branch and Bound (B&B). The "LC" in LC Branch and Bound stands for "Linear Cutting," which refers to the use of linear programming relaxations to generate bounds and cuts.

The Branch and Bound method is a popular optimization technique used to solve discrete optimization problems. It works by recursively partitioning the solution space into smaller sub-problems, solving each sub-problem, and then combining the solutions to obtain the optimal solution. However, the B&B method can be slow and inefficient, especially for large problems.

The LC Branch and Bound method addresses this limitation by incorporating linear programming relaxations into the B&B framework. By solving LP relaxations, the algorithm can generate tighter bounds and cuts, which help to prune the search space and reduce the number of nodes to be explored. This results in a significant reduction in computational time and memory usage.

How LC Branch and Bound Works

The LC Branch and Bound algorithm can be broken down into the following steps:

Step 1: Problem Formulation

The algorithm starts by formulating the optimization problem as a Mixed-Integer Linear Program (MILP). The MILP is a mathematical model that represents the problem using linear equations and inequalities, with some variables restricted to be integers.

Step 2: Linear Programming Relaxation

The algorithm solves the LP relaxation of the MILP, which is obtained by dropping the integrality constraints. The LP relaxation provides a lower bound on the optimal solution, which is used to prune the search space.

Step 3: Branching

The algorithm selects a node from the search tree and applies branching rules to create two child nodes. The branching rules are designed to partition the solution space into smaller sub-problems.

Step 4: Bounding

The algorithm solves the LP relaxation of each child node and computes a lower bound on the optimal solution. The lower bound is used to prune the search space and eliminate nodes that are unlikely to contain the optimal solution.

Step 5: Cutting

The algorithm applies cutting plane methods to generate additional constraints that help to tighten the LP relaxation. The cutting planes are used to reduce the search space and improve the lower bound.

Step 6: Fathoming

The algorithm applies fathoming rules to eliminate nodes that are unlikely to contain the optimal solution. Fathoming is based on the lower bound and the gap between the lower bound and the incumbent solution.

Step 7: Repeat

The algorithm repeats steps 3-6 until the optimal solution is found or a stopping criterion is reached.

Advantages of LC Branch and Bound

The LC Branch and Bound method offers several advantages over traditional optimization techniques:

Improved Computational Efficiency

The LC Branch and Bound method is computationally efficient, especially for large problems. By using LP relaxations and cutting planes, the algorithm can reduce the search space and prune nodes that are unlikely to contain the optimal solution.

Tighter Bounds

The LC Branch and Bound method provides tighter bounds on the optimal solution, which helps to reduce the search space and improve the convergence rate.

Flexibility

The LC Branch and Bound method can be applied to a wide range of optimization problems, including MILPs, integer programs, and stochastic programs.

Applications of LC Branch and Bound

The LC Branch and Bound method has been successfully applied to a wide range of optimization problems, including:

The LC Branch and Bound method has been used to solve complex scheduling problems, such as job shop scheduling and flow shop scheduling.

Logistics and Supply Chain Management

The LC Branch and Bound method has been used to optimize logistics and supply chain management problems, such as vehicle routing and inventory management.

Energy and Resource Allocation

The LC Branch and Bound method has been used to optimize energy and resource allocation problems, such as power grid management and resource allocation in cloud computing.

In this blog post, we have explored the principles and applications of the LC Branch and Bound method in DAA. This powerful optimization technique has been shown to be effective in solving complex optimization problems, including MILPs, integer programs, and stochastic programs. By combining the strengths of LP relaxations and Branch and Bound, the LC Branch and Bound method provides a robust and efficient framework for solving optimization problems.

• [1] Nemhauser, G. L., & Wolsey, L. A. (1988). Integer and combinatorial optimization. Wiley-Interscience.
• [2] Parker, R. G., & Rardin, R. L. (1988). Discrete optimization. Academic Press.
• [3] Geoffrion, A. M. (1972). Generalized Benders decomposition. Journal of Optimization Theory and Applications, 10(4), 237-260.

Q: What is the main advantage of the LC Branch and Bound method?

A: The main advantage of the LC Branch and Bound method is its ability to solve complex optimization problems efficiently, especially for large problems.

Q: How does the LC Branch and Bound method differ from traditional Branch and Bound?

A: The LC Branch and Bound method differs from traditional Branch and Bound in its use of LP relaxations and cutting planes to generate tighter bounds and prune the search space.

Q: What types of problems can be solved using the LC Branch and Bound method?

A: The LC Branch and Bound method can be used to solve a wide range of optimization problems, including MILPs, integer programs, and stochastic programs.

• Branch and Bound Tutorial
• Backtracking Vs Branch-N-Bound
• 0/1 Knapsack
• 8 Puzzle Problem
• Job Assignment Problem
• N-Queen Problem
• Travelling Salesman Problem

Introduction to Branch and Bound – Data Structures and Algorithms Tutorial

Branch and bound algorithms are used to find the optimal solution for combinatory, discrete, and general mathematical optimization problems. A branch and bound algorithm provide an optimal solution to an NP-Hard problem by exploring the entire search space. Through the exploration of the entire search space, a branch and bound algorithm identify possible candidates for solutions step-by-step.

There are many optimization problems in computer science, many of which have a finite number of the feasible shortest path in a graph or minimum spanning tree that can be solved in polynomial time. Typically, these problems require a worst-case scenario of all possible permutations. The branch and bound algorithm create branches and bounds for the best solution.

In this tutorial, we’ll discuss the branch and bound method in detail.

Different search techniques in branch and bound:

The Branch  algorithms incorporate different search techniques to traverse a state space tree. Different search techniques used in B&B are listed below:

1. LC search (Least Cost Search):

It uses a heuristic cost function to compute the bound values at each node. Nodes are added to the list of live nodes as soon as they get generated. The node with the least value of a cost function selected as a next E-node.

2.BFS(Breadth First Search): It is also known as a FIFO search. It maintains the list of live nodes in first-in-first-out order i.e, in a queue, The live nodes are searched in the FIFO order to make them next E-nodes.

3. DFS (Depth First Search): It is also known as a LIFO search. It maintains the list of live nodes in last-in-first-out order i.e. in a stack.

The live nodes are searched in the LIFO order to make them next E-nodes.

Introduction to Branch and Bound

When to apply Branch and Bound Algorithm?

Branch and bound is an effective solution to some problems, which we have already discussed. We’ll discuss all such cases where branching and binding are appropriate in this section.

• It is appropriate to use a branch and bound approach if the given problem is discrete optimization. Discrete optimization refers to problems in which the variables belong to the discrete set. Examples of such problems include 0-1 Integer Programming and Network Flow problems.
• When it comes to combinatory optimization problems, branch and bound work well. An optimization problem is optimized by combinatory optimization by finding its maximum or minimum based on its objective function. The combinatory optimization problems include Boolean Satisfiability and Integer Linear Programming.

Basic Concepts of Branch and Bound:

▸ Generation of a state space tree:

As in the case of backtracking, B&B generates a state space tree to efficiently search the solution space of a given problem instance.

In B&B, all children of an E-node in a state space tree are produced before any live node gets converted in an E-node. Thus, the E-node remains an E-node until i becomes a dead node.

• Evaluation of a candidate solution:

Unlike backtracking, B&B needs additional factors evaluate a candidate solution:

• A way to assign a bound on the best values of the given criterion functions to each node in a state space tree: It is produced by the addition of further components to the partial solution given by that node.
• The best values of a given criterion function obtained so far: It describes the upper bound for the maximization problem and the lower bound for the minimization problem.
• A feasible solution is defined by the problem states that satisfy all the given constraints.
• An optimal solution is a feasible solution, which produces the best value of a given objective function.
• Bounding function :

It optimizes the search for a solution vector in the solution space of a given problem instance.

It is a heuristic function that evaluates the lower and upper bounds on the possible solutions at each node. The bound values are used to search the partial solutions leading to an optimal solution. If a node does not produce a solution better than the best solution obtained thus far, then it is abandoned without further exploration.

The algorithm then branches to another path to get a better solution. The desired solution to the problem is the value of the best solution produced so far.

▸ The reasons to dismiss a search path at the current node :

(i) The bound value of the node is lower than the upper bound in the case of the maximization problem and higher than the lower bound in the case of the minimization problem. (i.e. the bound value of the ade is not better than the value of the best solution obtained until that node).

(ii) The node represents infeasible solutions, de violation of the constraints of the problem.

(iii) The node represents a subset of a feasible solution containing a single point. In this case, if the latest solution is better than the best solution obtained so far the best solution is modified to the value of a feasible solution at that node.

Types of Branch and Bound Solutions:

The solution of the Branch and the bound problem can be represented in two ways:

• Variable size solution: Using this solution, we can find the subset of the given set that gives the optimized solution to the given problem. For example, if we have to select a combination of elements from {A, B, C, D} that optimizes the given problem, and it is found that A and B together give the best solution, then the solution will be {A, B}.
• Fixed-size solution: There are 0s and 1s in this solution, with the digit at the ith position indicating whether the ith element should be included, for the above example, the solution will be given by {1, 1, 0, 0}, here 1 represent that we have select the element which at ith position and 0 represent we don’t select the element at ith position.

Classification of Branch and Bound Problems:

The Branch and Bound method can be classified into three types based on the order in which the state space tree is searched. 

• FIFO Branch and Bound
• LIFO Branch and Bound
• Least Cost-Branch and Bound

We will now discuss each of these methods in more detail. To denote the solutions in these methods, we will use the variable solution method.

1. FIFO Branch and Bound

First-In-First-Out is an approach to the branch and bound problem that uses the queue approach to create a state-space tree. In this case, the breadth-first search is performed, that is, the elements at a certain level are all searched, and then the elements at the next level are searched, starting with the first child of the first node at the previous level.

For a given set {A, B, C, D}, the state space tree will be constructed as follows :

State Space tree for set {A, B, C, D}

The above diagram shows that we first consider element A, then element B, then element C and finally we’ll consider the last element which is D. We are performing BFS while exploring the nodes.

So, once the first level is completed. We’ll consider the first element, then we can consider either B, C, or D. If we follow the route then it says that we are doing elements A and D so we will not consider elements B and C. If we select the elements A and D only, then it says that we are selecting elements A and D and we are not considering elements B and C.

Selecting element A

Now, we will expand node 3, as we have considered element B and not considered element A, so, we have two options to explore that is elements C and D. Let’s create nodes 9 and 10 for elements C and D respectively.

Considered element B and not considered element A

Now, we will expand node 4 as we have only considered elements C and not considered elements A and B, so, we have only one option to explore which is element  D. Let’s create node 11 for D.

 Considered elements C and not considered elements A and B

Till node 5, we have only considered elements D, and not selected elements A, B, and C. So, We have no more elements to explore, Therefore on node 5, there won’t be any expansion.

Now, we will expand node 6 as we have considered elements A and B, so, we have only two option to explore that is element C and D. Let’s create node 12 and 13 for C and D respectively.

Expand node 6

Now, we will expand node 7 as we have considered elements A and C and not consider element B, so, we have only one option to explore which is element  D. Let’s create node 14 for D.

Expand node 7

Till node 8, we have considered elements A and D, and not selected elements B and C, So, We have no more elements to explore, Therefore on node 8, there won’t be any expansion.

Now, we will expand node 9 as we have considered elements B and C and not considered element A, so, we have only one option to explore which is element  D. Let’s create node 15 for D.

Expand node 9

2. LIFO Branch and Bound

The Last-In-First-Out approach for this problem uses stack in creating the state space tree. When nodes are added to a state space tree, they are added to a stack. After all nodes of a level have been added, we pop the topmost element from the stack and explore it.

State space tree for element {A, B, C, D}

Now the expansion would be based on the node that appears on the top of the stack. Since node 5 appears on the top of the stack, so we will expand node 5. We will pop out node 5 from the stack. Since node 5 is in the last element, i.e., D so there is no further scope for expansion.

The next node that appears on the top of the stack is node 4. Pop-out node 4 and expand. On expansion, element D will be considered and node 6 will be added to the stack shown below:

Expand node 4

The next node is 6 which is to be expanded. Pop-out node 6 and expand. Since node 6 is in the last element, i.e., D so there is no further scope for expansion.

The next node to be expanded is node 3. Since node 3 works on element B so node 3 will be expanded to two nodes, i.e., 7 and 8 working on elements C and D respectively. Nodes 7 and 8 will be pushed into the stack.

The next node that appears on the top of the stack is node 8. Pop-out node 8 and expand. Since node 8 works on element D so there is no further scope for the expansion.

Expand node 3

The next node that appears on the top of the stack is node 7. Pop-out node 7 and expand. Since node 7 works on element C so node 7 will be further expanded to node 9 which works on element D and node 9 will be pushed into the stack.

The next node that appears on the top of the stack is node 9. Since node 9 works on element D, there is no further scope for expansion.

The next node that appears on the top of the stack is node 2. Since node 2 works on the element A so it means that node 2 can be further expanded. It can be expanded up to three nodes named 10, 11, 12 working on elements B, C, and D respectively. There new nodes will be pushed into the stack shown as below:

Expand node 2

In the above method, we explored all the nodes using the stack that follows the LIFO principle.

3. Least Cost-Branch and Bound

To explore the state space tree, this method uses the cost function. The previous two methods also calculate the cost function at each node but the cost is not been used for further exploration.

In this technique, nodes are explored based on their costs, the cost of the node can be defined using the problem and with the help of the given problem, we can define the cost function. Once the cost function is defined, we can define the cost of the node. Now, Consider a node whose cost has been determined. If this value is greater than U0, this node or its children will not be able to give a solution. As a result, we can kill this node and not explore its further branches. As a result, this method prevents us from exploring cases that are not worth it, which makes it more efficient for us. 

Let’s first consider node 1 having cost infinity shown below:

In the following diagram, node 1 is expanded into four nodes named 2, 3, 4, and 5.

Node 1 is expanded into four nodes named 2, 3, 4, and 5

Assume that cost of the nodes 2, 3, 4, and 5 are 12, 16, 10, and 315 respectively. In this method, we will explore the node which is having the least cost. In the above figure, we can observe that the node with a minimum cost is node 4. So, we will explore node 4 having a cost of 10.

During exploring node 4 which is element C, we can notice that there is only one possible element that remains unexplored which is D (i.e, we already decided not to select elements A, and B). So, it will get expanded to one single element D, let’s say this node number is 6.

Exploring node 4 which is element C

Now, Node 6 has no element left to explore. So, there is no further scope for expansion. Hence the element {C, D} is the optimal way to choose for the least cost.

Problems that can be solved using Branch and Bound Algorithm:

The Branch and Bound method can be used for solving most combinatorial problems. Some of these problems are given below:

Advantages of Branch and Bound Algorithm:

• We don’t explore all the nodes in a branch and bound algorithm. Due to this, the branch and the bound algorithm have a lower time complexity than other algorithms.
• Whenever the problem is small and the branching can be completed in a reasonable amount of time, the algorithm finds an optimal solution.
• By using the branch and bound algorithm, the optimal solution is reached in a minimal amount of time. When exploring a tree, it does not repeat nodes.

Disadvantages of Branch and Bound Algorithm:

• It takes a long time to run the branch and bound algorithm. 
• In the worst-case scenario, the number of nodes in the tree may be too large based on the size of the problem.

The branch and bound algorithms are one of the most popular algorithms used in optimization problems that we have discussed in our tutorial. We have also explained when a branch and bound algorithm is appropriate for a user to use. In addition, we presented an algorithm based on branches and bounds for assigning jobs. Lastly, we discussed some advantages and disadvantages of branch and bound algorithms.

Please Login to comment...

Similar reads.

• Branch and Bound
• Data Structures
• DSA Tutorials
• 105 Funny Things to Do to Make Someone Laugh
• Best PS5 SSDs in 2024: Top Picks for Expanding Your Storage
• Best Nintendo Switch Controllers in 2024
• Xbox Game Pass Ultimate: Features, Benefits, and Pricing in 2024
• #geekstreak2024 – 21 Days POTD Challenge Powered By Deutsche Bank

Improve your Coding Skills with Practice

What kind of Experience do you want to share?

Navigation Menu

Search code, repositories, users, issues, pull requests..., provide feedback.

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly.

To see all available qualifiers, see our documentation .

• Notifications You must be signed in to change notification settings

Programming assignments of NPTEL DAA course taken by Prof. Madhavan Mukund of Chennai Mathematical Institute.

souraavv/NPTEL-DAA-Programming-Assignment-Solutions

Folders and files.

Repository files navigation

Request: Try these yourself till the deadline of assignment. Only after the deadline look for the solution. Else it won't help you in learning. The reason to put solution is to help after assignment deadline not during assignment.

Sourav Sharma (UIIT Shimla)

NPTEL-Design Analysis And Algorithm - Programming Assignments Solutions

Certificate Link : Click here

Editorial for some of the programming problems : Click here

Browse Course Material

Course info, instructors.

• Prof. Erik Demaine
• Prof. Srini Devadas
• Prof. Nancy Lynch

Departments

• Electrical Engineering and Computer Science
• Mathematics

As Taught In

• Algorithms and Data Structures
• Computer Networks
• Cryptography
• Applied Mathematics

Learning Resource Types

Design and analysis of algorithms, assignments, problem sets.

Ten problem sets will be assigned during the semester.

Problem sets should be submitted in PDF format. Formatting your problem set in LaTeX will make it easier for us to read; however, any method of generating the PDF is acceptable (including scanning handwritten documents), as long as it is clearly legible.

The problem sets include exercises that should be solved but not handed in. These questions are intended to help you master the course material and will be useful in solving the assigned problems. Material covered in exercises will be tested on exams.

Guide to Writing Up Homework

You should be as clear and precise as possible in your write-up of solutions. Understandability of your answer is as desirable as correctness, because communication of technical material is an important skill.

A simple, direct analysis is worth more points than a convoluted one, both because it is simpler and less prone to error and because it is easier to read and understand. Sloppy answers will receive fewer points, even if they are correct, so make sure that your handwriting and your thoughts are legible. If writing your problem set by hand, it is a good idea to copy over your solutions to hand in, which will make your work neater and give you a chance to do sanity checks and correct bugs. If typesetting, reviewing the problem set while typing it in often has this effect. In either case, going over your solution at least once before submitting it is strongly recommended.

You will often be called upon to “give an algorithm” to solve a certain problem. Your write-up should take the form of a short essay. A topic paragraph should summarize the problem you are solving and what your results are. The body of your essay should provide the following:

• A description of the algorithm in English and, if helpful, pseudocode.
• At least one worked example or diagram to show more precisely how your algorithm works.
• A proof (or indication) of the correctness of the algorithm.
• An analysis of the running time of the algorithm.

Remember, your goal is to communicate. Graders will be instructed to take off points for convoluted and obtuse descriptions.

LaTeX Template for Problem Sets (ZIP) (This file contains: 1 .cls file, 2 .sty files, 1 .pdf file and 1 .tex file.)

You are leaving MIT OpenCourseWare

• Create Account

Design and Analysis of Algorithms

This course introduces basic elements of the design and analysis of computer algorithms. Topics include asymptotic notations and analysis, divide and conquer strategy, greedy methods, dynamic programming, basic graph algorithms, NP-completeness, and approximation algorithms. For each topic, beside in-depth coverage, one or more representative problems and their algorithms shall be discussed.

• Question Banks
• DAA Model question
• DAA Question Bank 2080
• DAA Question Bank 2079
• DAA Question Bank 2076
• DAA Question Bank 2078

Tribhuvan University

Institute of Science and Technology

Bachelor Level / fifth-semester / Science

Computer Science and Information Technology( CSC314 )

Full Marks: 60 + 20 + 20

Pass Marks: 24 + 8 + 8

Time: 3 Hours

Candidates are required to give their answers in their own words as far as practicable.

The figures in the margin indicate full marks.

Attempt any two questions.

What is recurrence relation? How it can be solved? Show that time complexity of the recurrence relation T(n) = 2T(n/2) + 1 is O(n) using substitution method.

Write down the advantages of dynamic programming over greedy strategy. Find optimal bracketing to multiply 4 matrices of order 2,3,4,2,5.

Discuss heapify operation with example. Write down its algorithm and analyze its time and space complexity.

Attempt any eight questions

Define RAM model. Write down iterative algorithm for finding factorial and provide its detailed analysis.

Write down algorithm of insertion sort and analyze its time and space complexity.

Write down minmax algorithm and analyze its complexity.

When greedy strategy provides optimal solution? Write down job sequencing with deadlines algorithm and analyze its complexity.

Suppose that a message contains alphabet frequencies as given below and find Huffman codes for each alphabet

Does backtracking give multiple solution? Trace subset sum algorithm for the set {3,5,2,4,1} andd sum=8.

Why extended euclidean algorithm is used? Write down its algorithm and analyze its complexity.

Define NP-complete problems with examples. Give brief proof of the statement “SAT is NP-complete”.

Write short notes on

a) Aggregate Analysis

b) Selection problems

Design and Analysis of Algorithms Question Bank Solution 2080

Share this link via

Or copy link

Copyright 2024 | HAMROCSIT.COM | All Right Reserved - Nymna Technology

• DAA Tutorial
• DAA Algorithm
• Need of Algorithm
• Complexity of Algorithm
• Algorithm Design Techniques
• Asymptotic Analysis
• Analyzing Algorithm Control Structure
• Recurrence Relation
• Recursion Tree Method
• Master Method

Analysis of Sorting

• Bubble Sort
• Selection Sort
• Insertion Sort

Divide and Conquer

• Introduction
• Max-Min Problem
• Binary Search
• Tower of Hanoi
• Binary Heap
• Stable Sorting
• Lower bound Theory

Sorting in Linear Time

• Linear Time
• Counting Sort
• Bucket Sort
• Hash Tables
• Hashing Method
• Open Addressing Techniques
• Hash Function

Binary Search Trees

• Red Black Tree
• Dynamic Programming
• Divide & Conquer Method vs Dynamic Programming
• Fibonacci sequence
• Matrix Chain Multiplication
• Matrix Chain Multiplication Example
• Matrix Chain Multiplication Algorithm
• Longest Common Sequence
• Longest Common Sequence Algorithm
• 0/1 Knapsack Problem
• DUTCH NATIONAL FLAG
• Longest Palindrome Subsequence
• Longest Increasing Subsequence
• Longest Common Subsequence
• Tabulation vs Memoization
• How to solve a dynamic programming problem
• Optimal Substructure Property
• Overlapping sub-problems
• Dynamic programming vs Greedy approach
• Regular Expression Matching
• Branch and bound vs backtracking
• Branch and bound
• Longest Repeated Subsequence
• Longest Common Substring
• Shortest Common Supersequence
• Dynamic Programming vs Divide and Conquer
• Maximum Sum Increasing Subsequence
• Wildcard Pattern Matching
• Largest Sum Contiguous Subarray
• Shortest Sum Contiguous Subarray
• Dynamic programming vs Backtracking
• Brute force approach
• Fractional vs 0/1 knapsack problem
• Traveling Salesperson problem using branch and bound
• Integer Partition Problem
• Kruskal Algorithm

Greedy Algorithm

• Greedy Algorithms
• Activity Selection Problem
• Fractional Knapsack problem
• Huffman Codes
• Algorithm of Huffman Code
• Activity or Task Scheduling Problem
• Travelling Sales Person Problem
• Dynamic Programming vs Greedy Method

Backtracking

• Backtracking Introduction
• Recursive Maze Algorithm
• Hamiltonian Circuit Problems
• Subset Sum Problems
• N Queens Problems
• MST Introduction
• MST Applications
• Kruskal's Algorithm
• Prim's Algorithm

Shortest Path

• Negative Weight Edges
• Representing Shortest Path
• Dijkstra's Algorithm
• Bellman-Ford Algorithm
• Single Source Shortest Path in a directed Acyclic Graphs

All-Pairs Shortest Paths

• Floyd-Warshall Algorithm
• Johnson's Algorithm

Maximum Flow

• Flow networks and Flows
• Network Flow Problems
• Ford Fulkerson Algorithm
• Maximum bipartite matching

Sorting Networks

• Comparison Network
• Bitonic Sorting Network
• Merging Network

Complexity Theory

• Complexity Classes
• Polynomial Time Verification
• NP-Completeness
• Circuit Satisfiability
• 3-CNF Satisfiability
• Clique Problem
• Vertex Cover Problem
• Subset-Sum Problem

Approximation Algo

• Vertex Cover
• Travelling Salesman Problem

String Matching

• Naive String Matching Algorithm
• Rabin-Karp-Algorithm
• String Matching with Finite Automata
• Knuth-Morris-Pratt Algorithm
• Boyer-Moore Algorithm
• Kosaraju Algorithm
• Hashing algorithm
• Huffman Coding Algorithm
• Kadane's Algorithm
• Dijkstra Algorithm Example
• Euclidean algorithm
• Floyd's Algorithm
• Properties of Algorithm
• Time Complexity of Kruskals Algorithm
• Kosaraju's Algorithm
• Characteristics of an Algorithm
• Algorithm Examples
• Searching Algorithms
• Algorithm for Binary Search
• Sorting Algorithms: Slowest to Fastest
• Extended Euclidian Algorithm
• How to Write an Algorithm
• Recursive Algorithm
• Sliding Window Algorithm
• Difference Between Algorithms and Flowcharts
• PageRank Algorithm
• Greedy Algorithm Example

Interview Questions

• DAA Interview Questions

Latest Courses

We provides tutorials and interview questions of all technology like java tutorial, android, java frameworks

Contact info

G-13, 2nd Floor, Sec-3, Noida, UP, 201301, India

[email protected] .

Online Compiler

Advertisement

A hybrid genetic algorithm with an adaptive diversity control technique for the homogeneous and heterogeneous dial-a-ride problem

• Original Research
• Published: 09 September 2024

Cite this article

• Somayeh Sohrabi 1 ,
• Koorush Ziarati   ORCID: orcid.org/0000-0001-7618-6807 1 &
• Morteza Keshtkaran 1  

28 Accesses

Explore all metrics

Dial-a-Ride Problem (DARP) is one of the classic routing problems with pairing and precedence constraints. Due to these types of constraints, it is quite challenging to design an efficient evolutionary algorithm for solving this problem. In this paper, a genetic algorithm in combination with a variable neighborhood descent procedure is suggested to solve the DARP. This algorithm, which is called Hybrid Genetic Algorithm (HGA), is independent of any repairing procedure or user-defined penalty factors. Instead, it uses the constraint dominance principle with respect to the number of unserved requests. Our algorithm employs an adaptive population management technique which takes into account not only the quality of solutions but also their contribution in the diversity level. To do so efficiently, this population management technique utilizes a simple arc-based representation for the DARP solutions. A route-based crossover procedure known as Route Exchange Crossover is used in the HGA. This crossover method is thoroughly compared with five other crossover techniques including a new one called Block Exchange Crossover. The HGA produces competitive solutions in comparison with the state-of-the-art methods for tackling the DARP and Heterogeneous DARP (H-DARP). It obtains the optimal solutions of all the small and medium size standard instances of the DARP and finds new best results for two large ones with unknown optimal solutions. Moreover, for 12 out of 24 new instances of the H-DARP, the best known solutions are improved using the HGA.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Subscribe and save.

• Get 10 units per month
• Download Article/Chapter or eBook
• 1 Unit = 1 Article or 1 Chapter
• Cancel anytime

Price includes VAT (Russian Federation)

Instant access to the full article PDF.

Rent this article via DeepDyve

Institutional subscriptions

Similar content being viewed by others

An Adaptive Multi-Crossover Population Algorithm for Solving Routing Problems

Modified DE Algorithms for Solving Multi-depot Vehicle Routing Problem with Multiple Pickup and Delivery Requests

Solving the Dial-a-Ride Problem Using an Adapted Genetic Algorithm

Explore related subjects.

• Artificial Intelligence

Atahran, A., Lenté, C., & T’kindt, V. (2014). A multicriteria dial-a-ride problem with an ecological measure and heterogeneous vehicles. Journal of Multi-Criteria Decision Analysis, 21 , 279–298.

Article   Google Scholar  

Braekers, K., Caris, A., & Janssens, G. K. (2014). Exact and meta-heuristic approach for a general heterogeneous dial-a-ride problem with multiple depots. Transportation Research Part B: Methodological, 67 , 166–186.

Chassaing, M., Duhamel, C., & Lacomme, P. (2016). An ELS-based approach with dynamic probabilities management in local search for the Dial-A-Ride Problem. Engineering Applications of Artificial Intelligence, 2 (48), 119–133.

Chevrier, R., Liefooghe, A., Jourdan, L., & Dhaenens, C. (2012). Solving a dial-a-ride problem with a hybrid evolutionary multi-objective approach: Application to demand responsive transport. Applied Soft Computing Journal, 4 (12), 1247–1258.

Cordeau, J. F. (2006). A branch-and-cut algorithm for the dial-a-ride problem. Operations Research, 5 (54), 573–586.

Cordeau, J. F., & Laporte, G. (2003). The Dial-a-Ride Problem (DARP): Variants, modeling issues and algorithms. Quarterly Journal of the Belgian, French and Italian Operations Research Societies, 1 , 89–101.

Google Scholar  

Cordeau, J. F., & Laporte, G. (2003). A tabu search heuristic for the static multi-vehicle dial-a-ride problem. Transportation Research Part B: Methodological, 37 , 579–594.

Cordeau, J. F., & Laporte, G. (2007). The dial-a-ride problem: Models and algorithms. Annals of Operations Research, 9 (153), 29–46.

Deb, K. (2000). An efficient constraint handling method for genetic algorithms. Computers Methods in Applied Mechanics and Engineering, 186 , 311–338.

Garcia-Najera, A., & Bullinaria, J. A. (2011). An improved multi-objective evolutionary algorithm for the vehicle routing problem with time windows (Vol. 38, pp. 287–300). Elsevier Ltd.

Gschwind, T., & Drexl, M. (2019). Adaptive large neighborhood search with a constant-time feasibility test for the dial-a-ride problem. Transportation Science, 3 (53), 480–491.

Ho, S. C., Szeto, W. Y., Kuo, Y. H., Leung, J. M. Y., Petering, M., & Tou, T. W. H. (2018). A survey of dial-a-ride problems: Literature review and recent developments. Transportation Research Part B: Methodological, 5 (111), 395–421.

Hunsaker, B., & Savelsbergh, M. (2002). Operations research letters EEcient feasibility testing for dial-a-ride problems. Operations Research Letters, 30 , 169–173.

Jorgensen, R. M., Larsen, J., & Bergvinsdottir, K. B. (2007). Solving the dial-a-ride problem using genetic algorithms. Journal of the Operational Research Society, 58 , 1321–1331.

Jozefowiez, N., Semet, F., & Talbi, E. G. (2009). An evolutionary algorithm for the vehicle routing problem with route balancing. European Journal of Operational Research, 6 (195), 761–769.

Karakatič, S., & Podgorelec, V. (2015). A survey of genetic algorithms for solving multi depot vehicle routing problem. Applied Soft Computing, 27 , 519–532.

Malheiros, I., Ramalho, R., Passeti, B., Bulhões, T., & Subramanian, A. (2021). A hybrid algorithm for the multi-depot heterogeneous dial-a-ride problem. Computers and Operations Research, 5 , 129.

Masmoudi, M. A., Braekers, K., Masmoudi, M., & Dammak, A. (2017). A hybrid genetic algorithm for the heterogeneous dial-A-ride problem. Computers and Operations Research, 5 (81), 1–13.

Mendoza, J. E., Castanier, B., Guéret, C., Medaglia, A. L., & Velasco, N. (2010). A memetic algorithm for the multi-compartment vehicle routing problem with stochastic demands. Computers and Operations Research, 11 (37), 1886–1898.

Molenbruch, Y., Braekers, K., & Caris, A. (2017). Typology and literature review for dial-a-ride problems. Annals of Operations Research, 12 (259), 295–325.

Mourad, A., Puchinger, J., & Chu, C. (2019). A survey of models and algorithms for optimizing shared mobility. Transportation Research Part B: Methodological, 5 (123), 323–346.

Núñez, A., Cortés, C. E., Sáez, D., Schutter, B. D., & Gendreau, M. (2014). Multiobjective model predictive control for dynamic pickup and delivery problems. Control Engineering Practice, 32 , 73–86.

Ombuki, B., Ross, B. J., & Hanshar, F. (2006). Multi-objective genetic algorithms for vehicle routing problem with time windows. Applied Intelligence, 24 , 17–30.

Parragh, S. N. (2011). Introducing heterogeneous users and vehicles into models and algorithms for the dial-a-ride problem. Transportation Research Part C: Emerging Technologies, 19 , 912–930.

Parragh, S. N., Doerner, K. F., & Hartl, R. F. (2010). Variable neighborhood search for the dial-a-ride problem. Computers and Operations Research, 6 (37), 1129–1138.

Parragh, S. N., & Schmid, V. (2013). Hybrid column generation and large neighborhood search for the dial-a-ride problem. Computers and Operations Research, 1 (40), 490–497.

Pereira, F. B., Tavares, J., Machado, P., & Costa, E. (2002). GVR: A new genetic representation for the vehicle routing problem. In M. O’Neill, R. F. E. Sutcliffe, C. Ryan, M. Eaton, & N. J. L. Griffith (Eds.), Artificial intelligence and cognitive science berlin (pp. 95–102). Springer.

Chapter   Google Scholar  

Potvin, J. Y., & Bengio, S. (1996). The vehicle routing problem with time windows part II: Genetic search. INFORMS Journal on Computing, 8 , 165–172.

Rahimi, I., Gandomi, A. H., Chen, F., & Mezura-Montes, E. (2023). A review on constraint handling techniques for population-based algorithms: From single-objective to multi-objective optimization. Archives of Computational Methods in Engineering, 4 (30), 2181–2209.

Ropke, S., Cordeau, J. F., & Laporte, G. (2007). Models and branch-and-cut algorithms for pickup and delivery problems with time windows. Networks: An International Journal, 49 , 258–272.

Ropke, S., & Pisinger, D. (2006). An adaptive large neighborhood search heuristic for the pickup and delivery problem with time windows. Transportation Science, 40 , 455–472.

Tan, K. C., Chew, Y. H., & Lee, L. H. (2006). A hybrid multiobjective evolutionary algorithm for solving vehicle routing problem with time windows. Computational Optimization and Applications, 5 (34), 115–151.

Toth, P., & Vigo, D. (2014). Vehicle routing . Society for Industrial and Applied Mathematics.

Book   Google Scholar  

Vidal, T. (2022). Hybrid genetic search for the CVRP: Open-source implementation and SWAP* neighborhood. Computers and Operations Research, 140 , 105643.

Vidal, T., Crainic, T. G., Gendreau, M., Lahrichi, N., & Rei, W. (2012). A hybrid genetic algorithm for multidepot and periodic vehicle routing problems. Operations Research, 5 (60), 611–624.

Vidal, T., Crainic, T. G., Gendreau, M., & Prins, C. (2013). A hybrid genetic algorithm with adaptive diversity management for a large class of vehicle routing problems with time-windows. Computers and Operations Research, 1 (40), 475–489.

Zhang, Z., Liu, M., & Lim, A. (2015). A memetic algorithm for the patient transportation problem. Omega, 7 (54), 60–71.

Download references

Acknowledgements

The authors would like to sincerely thank Professor Kris Braekers for sharing the code of the DA. Besides, we are extremely grateful to Professor Anand Subramanian and his colleagues for executing the HILS code considering the new H-DARP instances.

Author information

Authors and affiliations.

Department of Computer Science, Engineering and Information Technology, Shiraz University, Shiraz, Iran

Somayeh Sohrabi, Koorush Ziarati & Morteza Keshtkaran

You can also search for this author in PubMed   Google Scholar

Corresponding author

Correspondence to Koorush Ziarati .

Additional information

Publisher's note.

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Supplementary Information

Below is the link to the electronic supplementary material.

Supplementary file 1 (pdf 88 KB)

Rights and permissions.

Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.

Reprints and permissions

About this article

Sohrabi, S., Ziarati, K. & Keshtkaran, M. A hybrid genetic algorithm with an adaptive diversity control technique for the homogeneous and heterogeneous dial-a-ride problem. Ann Oper Res (2024). https://doi.org/10.1007/s10479-024-06194-z

Download citation

Received : 04 November 2023

Accepted : 26 July 2024

Published : 09 September 2024

DOI : https://doi.org/10.1007/s10479-024-06194-z

Share this article

Anyone you share the following link with will be able to read this content:

Sorry, a shareable link is not currently available for this article.

Provided by the Springer Nature SharedIt content-sharing initiative

• On-demand deliveries
• Shared mobility systems
• Pickup and delivery problem (PDP)
• Dial-a-ride problem (DARP)
• Genetic algorithm
• Population management
• Find a journal
• Publish with us
• Track your research

Information

• Author Services

Initiatives

You are accessing a machine-readable page. In order to be human-readable, please install an RSS reader.

All articles published by MDPI are made immediately available worldwide under an open access license. No special permission is required to reuse all or part of the article published by MDPI, including figures and tables. For articles published under an open access Creative Common CC BY license, any part of the article may be reused without permission provided that the original article is clearly cited. For more information, please refer to https://www.mdpi.com/openaccess .

Feature papers represent the most advanced research with significant potential for high impact in the field. A Feature Paper should be a substantial original Article that involves several techniques or approaches, provides an outlook for future research directions and describes possible research applications.

Feature papers are submitted upon individual invitation or recommendation by the scientific editors and must receive positive feedback from the reviewers.

Editor’s Choice articles are based on recommendations by the scientific editors of MDPI journals from around the world. Editors select a small number of articles recently published in the journal that they believe will be particularly interesting to readers, or important in the respective research area. The aim is to provide a snapshot of some of the most exciting work published in the various research areas of the journal.

Original Submission Date Received: .

• Active Journals
• Find a Journal
• Proceedings Series
• For Authors
• For Reviewers
• For Editors
• For Librarians
• For Publishers
• For Societies
• For Conference Organizers
• Open Access Policy
• Institutional Open Access Program
• Special Issues Guidelines
• Editorial Process
• Research and Publication Ethics
• Article Processing Charges
• Testimonials
• Preprints.org
• SciProfiles
• Encyclopedia

Article Menu

• Subscribe SciFeed
• Recommended Articles
• Google Scholar
• on Google Scholar
• Table of Contents

Find support for a specific problem in the support section of our website.

Please let us know what you think of our products and services.

Visit our dedicated information section to learn more about MDPI.

JSmol Viewer

Comprehensive task optimization architecture for urban uav-based intelligent transportation system.

1. Introduction

• Advertisement (P 1 ): the auctioneer broadcasts the task to the robots of the network.
• Bidding (P 2 ): each robot undergoes a task valuation process and sends its bid to the auctioneer.
• Award (P 3 ): the auctioneer selects the most suitable robot for the task based on all the received bids for that task.
• Acknowledgment (P 4 ): each robot acknowledges the assignment to the auctioneer.
• Formalization of an original drone delivery problem (DDP) with charging hubs, including risk-aware route planning, dynamic task allocation, and balance of number of assigned tasks to each UAV.
• Development of a comprehensive allocation framework for tackling the formulated problem, optimizing energy efficiency, risk of flyable paths, and flight time.
• Inclusion of a redundant allocation strategy within the formulated architecture to address lossy communication scenarios.

2. Problem Statement

• The multi-robot system consists of multi-rotor UAVs operating in a well-defined populated urban operational area with charging stations.
• The task set consists of payload transportation tasks within the operational area. Each task is defined as the transportation of a payload mass from a pick-up location to a delivery location within a delivery time window.
• Minimize the total energy consumption required by the UAVs to execute all tasks.
• Minimize the discrepancy in the number of allocated tasks to each drone, i.e., maximize the workload homogeneity in the fleet of UAVs.
• Enable the allocation of dynamic tasks with higher priority with respect to the “regular” set of transportation tasks. An example is represented by the unexpected aerial delivery of medical samples to a hospital located in the operational area.
• Maximize the safety of the community and the feasibility of deployment of the aerial system in the real world by predicting risk-aware flyable paths to be executed by the UAVs [ 31 ].
• The payload capacity of a UAV equals its mass.
• A UAV can carry one payload at a time.
• A UAV cannot visit a charge station in loaded conditions.
• At the beginning of the delivery process, the UAVs are fully charged.
• The UAV re-charge time is the sum of the battery re-charge time (linearly interpolated from the residual battery level of the UAV) and the time needed by the UAV to reach the charge hub.
• A delivery task consists of six consecutive phases: unloaded UAV take-off, unloaded UAV cruise, unloaded UAV landing (the parcel pick-up phase takes place in unloaded conditions), loaded UAV take-off, loaded UAV cruise, and loaded UAV landing (the parcel delivery phase takes place in loaded conditions).
• A re-charge task consists of three consecutive phases: UAV take-off, UAV cruise, and UAV landing. In this case, no payload is carried by the UAV.
• UAVs maintain constant velocity throughout each phase of task execution, i.e., UAVs ascend at constant speed, cruise at constant speed, etc.
• UAV tilt angles are small throughout the flight.
• Turbulent atmospheric phenomena are neglected.

3. Task Allocation Architecture

3.1. market-based task scheduling.

3.2. Risk-Aware Path Planning

3.3. energy consumption model, 3.4. numerical optimization.

4. Simulation Results

• Scenario S A : T M I N = 0 , and random initialization of the following parameters: initial U L , delivery tasks’ pick-up and delivery locations, h associated to each task, re-charge hubs’ locations, and T M A X (within the range of 0 ,   3 h).
• Scenario S A ∗ : analogous to S A , but with no resource sharing in the allocation strategy and with each phase of task execution being completed at maximum speed.
• Scenario S B : random initialization of the following parameters: initial U L , delivery tasks’ pick-up and delivery locations, h associated to each task, re-charge hubs’ locations, T M A X (within the range of 0 ,   3   h), and T M I N (within the range of [ 1 ,   3 ] h).
• Scenario S B ∗ : analogous to S B , but with no resource sharing in the allocation strategy and with each phase of task execution being completed at maximum speed.
• The proposed architecture successfully tackled the formulated DDP with real-world instances of the problem itself.
• The main allocation objective of minimizing the energy consumption, despite being less favorable for the maximization of the number of completed tasks, did not compromise the level of performance of the allocation output.
• The proposed architecture was highly modular, flexible, and easily adaptable to tackle other task assignment problems with different objectives in the context of drone-based ITSs.
• Even with more demanding problem instances, such as scenario S B ∗ , the allocation architecture’s features of energy optimization, resource sharing, and dynamic task assignment did not compromise the overall level of performance of the architecture itself.
• The redundancy added in the allocation strategy enhanced the performances in case of lossy communication scenarios.

5. Conclusions

Author contributions, data availability statement, acknowledgments, conflicts of interest, nomenclature.

• Menouar, H.; Guvenc, I.; Akkaya, K.; Uluagac, A.S.; Kadri, A.; Tuncer, A. UAV-Enabled Intelligent Transportation Systems for the Smart City: Applications and Challenges. IEEE Commun. Mag. 2017 , 55 , 22–28. [ Google Scholar ] [ CrossRef ]
• Watkins, S.; Burry, J.; Mohamed, A.; Marino, M.; Prudden, S.; Fisher, A.; Kloet, N.; Jakobi, T.; Clothier, R. Ten questions concerning the use of drones in urban environments. Build. Environ. 2020 , 167 , 106458. [ Google Scholar ] [ CrossRef ]
• Guo, J.; Chen, L.; Li, L.; Na, X.; Vlacic, L.; Wang, F.Y. Advanced Air Mobility: An Innovation for Future Diversified Transportation and Society. IEEE Trans. Intell. Veh. 2024 , 9 , 3106–3110. [ Google Scholar ] [ CrossRef ]
• Straubinger, A.; de Groot, H.L.; Verhoef, E.T. E-commerce, delivery drones and their impact on cities. Transp. Res. Part A Policy Pract. 2023 , 178 , 103841. [ Google Scholar ] [ CrossRef ]
• Pons-Prats, J.; Živojinović, T.; Kuljanin, J. On the understanding of the current status of urban air mobility development and its future prospects: Commuting in a flying vehicle as a new paradigm. Transp. Res. Part E Logist. Transp. Rev. 2022 , 166 , 102868. [ Google Scholar ] [ CrossRef ]
• He, Y.; Wang, D.; Huang, F.; Zhang, R.; Min, L. Aerial-Ground Integrated Vehicular Networks: A UAV-Vehicle Collaboration Perspective. IEEE Trans. Intell. Transp. Syst. 2024 , 25 , 5154–5169. [ Google Scholar ] [ CrossRef ]
• Hu, Z.; Chen, H.; Lyons, E.J.; Solak, S.; Zink, M. Towards sustainable UAV operations: Balancing economic optimization with environmental and social considerations in path planning. Transp. Res. Part E Logist. Transp. Rev. 2024 , 181 , 103314. [ Google Scholar ] [ CrossRef ]
• Zarbakhshnia, N.; Ma, Z. Critical Success Factors for the Adoption of AVs in Sustainable Urban Transportation. Transp. Policy 2024 , 156 , 62–76. [ Google Scholar ] [ CrossRef ]
• Telikani, A.; Sarkar, A.; Du, B.; Shen, J. Machine Learning for UAV-Aided ITS: A Review with Comparative Study. IEEE Trans. Intell. Transp. Syst. 2024 , 1–19. [ Google Scholar ] [ CrossRef ]
• Rinaldi, M.; Primatesta, S.; Guglieri, G.; Rizzo, A. Auction-based Task Allocation for Safe and Energy Efficient UAS Parcel Transportation. Transp. Res. Procedia 2022 , 65 , 60–69. [ Google Scholar ] [ CrossRef ]
• Tomasicchio, G.; Cedrone, A.; Fiorini, F.; Esposito, L.; Scardapane, G.; Filipponi, F.; Rinaldi, M.; Primatesta, S. Resilient Drone Mission Management and Route Optimization in Drone Delivery Context. In Proceedings of the 28th Ka and Broadband Communications Conference (Ka), Bradford, UK, 23–26 October 2023. [ Google Scholar ]
• Rinaldi, M.; Primatesta, S.; Bugaj, M.; Rostáš, J.; Guglieri, G. Development of Heuristic Approaches for Last-Mile Delivery TSP with a Truck and Multiple Drones. Drones 2023 , 7 , 407. [ Google Scholar ] [ CrossRef ]
• Poudel, S.; Moh, S. Task assignment algorithms for unmanned aerial vehicle networks: A comprehensive survey. Veh. Commun. 2022 , 35 , 100469. [ Google Scholar ] [ CrossRef ]
• Jia, X.; Meng, M.Q.-H. A survey and analysis of task allocation algorithms in multi-robot systems. In Proceedings of the 2013 International Conference on Robotics and Biomimetics (ROBIO), Shenzhen, China, 12–14 December 2013. [ Google Scholar ]
• Skaltsis, G.M.; Shin, H.S.; Tsourdos, A. A survey of task allocation techniques in MAS. In Proceedings of the 2021 International Conference on Unmanned Aircraft Systems (ICUAS), Athens, Greece, 15–18 June 2021. [ Google Scholar ]
• Khamis, A.; Hussein, A.; Elmogy, A. Multi-robot task allocation: A review of the state-of-the-art. Stud. Comput. Intell. 2015 , 604 , 31–51. [ Google Scholar ]
• Nishira, M.; Ito, S.; Nishikawa, H.; Kong, X.; Tomiyama, H. An Integer Programming Based Approach to Delivery Drone Routing under Load-Dependent Flight Speed. Drones 2023 , 7 , 320. [ Google Scholar ] [ CrossRef ]
• Huang, H.; Hu, C.; Zhu, J.; Wu, M.; Malekian, R. Stochastic Task Scheduling in UAV-Based Intelligent On-Demand Meal Delivery System. IEEE Trans. Intell. Transp. Syst. 2022 , 23 , 13040–13054. [ Google Scholar ] [ CrossRef ]
• Cheng, Q.; Yin, D.; Yang, J.; Shen, L. An Auction-Based Multiple Constraints Task Allocation Algorithm for Multi-UAV System. In Proceedings of the 2016 International Conference on Cybernetics, Robotics and Control (CRC), Hong Kong, China, 19–21 August 2016. [ Google Scholar ]
• Qiu, Y.; Jiang, H.; Li, Q.; Dong, X.; Ren, Z. Application of an Adapted Genetic Algorithm on Task Allocation Problem of Multiple UAVs. In Proceedings of the 2018 CSAA Guidance, Navigation and Control Conference (CGNCC), Xiamen, China, 10–12 August 2018. [ Google Scholar ]
• Hu, X.; Wong, K.K.; Yang, K.; Zheng, Z. Task and Bandwidth Allocation for UAV-Assisted Mobile Edge Computing with Trajectory Design. In Proceedings of the 2019 Global Communications Conference (GLOBECOM), Waikoloa, HI, USA, 9–13 December 2019. [ Google Scholar ]
• Otte, M.; Kuhlman, M.J.; Sofge, D. Auctions for multi-robot task allocation in communication limited environments. Auton. Robot. 2020 , 44 , 547–584. [ Google Scholar ] [ CrossRef ]
• Cao, L.; Tan, H.S.; Peng, H.; Pan, M.C. Multiple UAVs hierarchical dynamic task allocation based on PSO-FSA and decentralized auction. In Proceedings of the 2014 IEEE International Conference on Robotics and Biomimetics (ROBIO), Bali, Indonesia, 5–10 December 2014. [ Google Scholar ]
• Sujit, P.B.; Beard, R. Distributed Sequential Auctions for Multiple UAV Task Allocation. In Proceedings of the 2007 American Control Conference, New York, NY, USA, 9–13 July 2007. [ Google Scholar ]
• Li, X.; Liang, Y. An Optimal Online Distributed Auction Algorithm for Multi-UAV Task Allocation. In Proceedings of the 11th International Conference on Logistics, Informatics and Service Sciences (LISS), Jinan, China, 23–26 July 2021. [ Google Scholar ]
• Sujit, P.B.; Beard, R. Multiple uav task allocation using distributed auctions. In Proceedings of the AIAA Guidance, Navigation and Control Conference and Exhibit, Hilton Head, CA, USA, 20–23 August 2007. [ Google Scholar ]
• Xu, S.; Yu, L.; Deng, X.; Tang, L. Task Allocation for Multiple Unmanned Aerial Vehicles Based on Combinatorial Auctions. In Proceedings of the 2021 IEEE International Conference on Unmanned Systems (ICUS), Beijing, China, 15–17 October 2021. [ Google Scholar ]
• Lee, C.W.; Wong, W.P. Last-mile drone delivery combinatorial double auction model using multi-objective evolutionary algorithms. Soft Comput. 2022 , 26 , 12355–12384. [ Google Scholar ] [ CrossRef ]
• Kim, J. Learning-based Second Price Auction for Distributed Delivery Scheduling in Smart and Autonomous Urban Air Mobility. In Proceedings of the 2022 13th International Conference on Ubiquitous and Future Networks (ICUFN), Barcelona, Spain, 5–8 July 2022. [ Google Scholar ]
• Rinaldi, M.; Primatesta, S.; Guglieri, G.; Rizzo, A. Multi-Auctioneer Market-based Task Scheduling for Persistent Drone Delivery. In Proceedings of the 2023 International Conference on Unmanned Aircraft Systems (ICUAS), Warsaw, PL, USA, 6–9 June 2023. [ Google Scholar ]
• Dalamagkidis, K.; Valavanis, K.P.; Piegl, L.A. On unmanned aircraft systems issues, challenges and operational restrictions preventing integration into the National Airspace System. Prog. Aerosp. Sci. 2008 , 44 , 503–519. [ Google Scholar ] [ CrossRef ]
• Primatesta, S.; Rizzo, A.; la Cour-Harbo, A. Ground risk map for unmanned aircraft in urban environments. J. Intell. Robot. Syst. 2020 , 97 , 489–509. [ Google Scholar ] [ CrossRef ]
• Primatesta, S.; Guglieri, G.; Rizzo, A. A risk-aware path planning strategy for UAVs in urban environments. J. Intell. Robot. Syst. 2019 , 95 , 629–643. [ Google Scholar ] [ CrossRef ]
• Karaman, S.; Frazzoli, E. Sampling-based algorithms for optimal motion planning. Int. J. Robot. Res. 2011 , 30 , 846–894. [ Google Scholar ] [ CrossRef ]
• Liu, Z.; Sengupta, R.; Kurzhanskiy, A. A power consumption model for multi-rotor small unmanned aircraft systems. In Proceedings of the 2017 International Conference on Unmanned Aircraft Systems (ICUAS), Miami, FL, USA, 13–16 June 2017. [ Google Scholar ]
• Byrne, C. Sequential unconstrained minimization algorithms for constrained optimization. Inverse Probl. 2008 , 24 , 015013. [ Google Scholar ] [ CrossRef ]
• Available online: https://www.researchgate.net/publication/255602767_Methods_for_Constrained_Optimization (accessed on 9 May 2024).
• Lagarias, J.C.; Reeds, J.A.; Wright, M.H.; Wright, P.E. Convergence Properties of the Nelder-Mead Simplex Method in Low Dimensions. SIAM J. Optim. 1998 , 9 , 112–147. [ Google Scholar ] [ CrossRef ]

Click here to enlarge figure

Share and Cite

Rinaldi, M.; Primatesta, S. Comprehensive Task Optimization Architecture for Urban UAV-Based Intelligent Transportation System. Drones 2024 , 8 , 473. https://doi.org/10.3390/drones8090473

Rinaldi M, Primatesta S. Comprehensive Task Optimization Architecture for Urban UAV-Based Intelligent Transportation System. Drones . 2024; 8(9):473. https://doi.org/10.3390/drones8090473

Rinaldi, Marco, and Stefano Primatesta. 2024. "Comprehensive Task Optimization Architecture for Urban UAV-Based Intelligent Transportation System" Drones 8, no. 9: 473. https://doi.org/10.3390/drones8090473

Article Metrics

Article access statistics, further information, mdpi initiatives, follow mdpi.

Subscribe to receive issue release notifications and newsletters from MDPI journals