Delivery Problem from Coursera

In this online course we’ll implement (in Python) together efficient programs for a problem needed by delivery companies all over the world millions times per day — the travelling salesman problem. The goal in this problem is to visit all the given places as quickly as possible. How to find an optimal solution to this problem quickly? We still don’t have provably efficient algorithms for this difficult computational problem and this is the essence of the P versus NP problem, the most important open question in Computer Science. Still, we’ll implement several solutions for real world instances of the travelling salesman problem.

While designing these solutions, we will rely heavily on the material learned in the courses of the specialization: proof techniques, combinatorics, probability, graph theory. We’ll see several examples of using discrete mathematics ideas to get more and more efficient solutions.

What's inside

Syllabus

Traveling Salesman Problem

We start this module with the definition of mathematical model of the delivery problem — the classical traveling salesman problem (usually abbreviated as TSP). We'll then review just a few of its many applications: from straightforward ones (delivering goods, planning a trip) to less obvious ones (data storage and compression, genome assembly). After that, we will together take the first steps in implementing programs for TSP.

Exact Algorithms

We'll see two general techniques applied to the traveling salesman problem. The first one, branch and bound, is a classical approach in combinatorial optimization that is used for various problems. It can be seen as an improvement of the brute force search: we try to construct a permutation piece by piece, but at each step we check whether it still makes sense to continue constructing the permutation (if it doesn't, we just cut off the current branch). The second one, dynamic programming, is arguably the most popular algorithmic technique. It solves a problem by going through a collection of smaller subproblems.

Approximation Algorithms

As we've seen in the previous modules, solving the traveling salesman problem exactly is hard. In fact, we don't even expect an efficient solution in the nearest future. For this reason, it makes sense to ask: is it possible to find efficiently a solution that is probably suboptimal, but at the same time is close to optimal? It turns out that the answer is yes! We'll learn two algorithms. The first one guarantees to find quickly a solution which is at most twice longer than the optimal one. The second algorithms does not have such guarantees, but it is known to work pretty well in practice.

Good to know

Know what's good

, what to watch for

, and possible dealbreakers

Explores efficient ways to address the traveling salesman problem, which is essential for delivery companies worldwide

Taught by Alexander S. Kulikov, a recognized expert in combinatorial optimization and algorithm design

Develops skills in proof techniques, combinatorics, probability, and graph theory, which are core foundations for computer science

Provides hands-on experience in implementing efficient programs for the traveling salesman problem

Examines the P versus NP problem, a central open question in computer science

Requires some background in computer science and mathematics

Reviews summary

Well-received course in delivery problems

learners say that this is a good and well-structured course on delivery problems, especially for beginners. Many students enjoyed the programming problems, puzzles, and quizzes.

Learners found the programming exercises to be helpful.

"Good exercises!"

"Very practical course a lot of things to learn."

"The code in examples is well written and clean."

Many students enjoyed this course.

"I liked it!"

"I am going to miss these professors a lot."

"I especially enjoyed the module on dynamic programming."

This course is a good fit for beginners.

"Very good course for beginners."

"Well structured introductory course"

"It's a great introductory course to these topics."

Some students felt that the course could have allowed learners to be more independent.

"The course could have allowed the learner to be more independent."

"I wasn't absolutely confident that I could repeat the results of the following in a similar circumstance."

Some learners found the content to be challenging.

"Too difficult compared with previous modules."

"Great course, but complex matters need to explained more slowly"

"I found that this required more advanced Python skills than I expected."

Activities

Be better prepared before your course. Deepen your understanding during and after it. Supplement your coursework and achieve mastery of the topics covered in Delivery Problem with these activities:

Organize Course Resources

Show steps

Improve your organization and note-taking skills while preparing for the course.

Show steps

Create a folder or notebook for course materials.
Organize materials into sections (e.g., notes, assignments, quizzes).

TSP Heuristics Tutorial

Show steps

Enhance your understanding of TSP heuristics by following guided tutorials.

Browse courses on Heuristics

Show steps

Find tutorials on TSP heuristics.
Follow the tutorials and implement the heuristics.

TSP Coding Challenges

Show steps

Develop your problem-solving and coding skills by working through TSP coding challenges.

Browse courses on Coding

Show steps

Find online TSP coding challenges.
Solve the challenges using your preferred programming language.

Four other activities

Expand to see all activities and additional details

Show all seven activities

Branch and Bound Algorithm for TSP

Show steps

Reinforce your understanding of the branch and bound algorithm and its application to solving the Traveling Salesman Problem.

Browse courses on Branch and Bound

Show steps

Review the fundamentals of the branch and bound algorithm.
Apply the branch and bound algorithm to a TSP problem.

The Traveling Salesman Problem: Algorithms and Applications

Show steps

Expand your understanding of the theoretical foundations and practical aspects of the Traveling Salesman Problem.

View Elements of Classical and Geometric Optimization on Amazon

Show steps

Read selected chapters to gain in-depth knowledge of TSP algorithms.

Interactive TSP Visualization

Show steps

Solidify your understanding of TSP by creating an interactive visualization that allows you to explore different solutions.

Show steps

Choose a programming language and framework.
Design the visualization interface.
Implement the TSP algorithm.
Test and refine the visualization.

Contribute to OpenTSP

Show steps

Gain practical experience and contribute to the TSP community by working on open-source projects.

Show steps

Identify areas to contribute to within OpenTSP.
Fork the OpenTSP repository.
Implement your contributions and submit a pull request.

Career center

Learners who complete Delivery Problem will develop knowledge and skills that may be useful to these careers:

Software Engineer

As a Software Engineer, you will be responsible for designing and developing software applications. The Delivery Problem course will help you learn how to apply computer science principles to solve real-world problems. This course will also help you develop the skills you need to work in a team environment and deliver high-quality software products.

See salaries and explore the career path for Software Engineer

Operations Research Analyst

As an Operations Research Analyst, you will use mathematical and analytical techniques to solve problems in a variety of industries. The Delivery Problem course will help you learn how to apply optimization techniques to real-world problems. This course will also help you develop the skills you need to communicate your findings to decision-makers.

See salaries and explore the career path for Operations Research Analyst

Data Scientist

As a Data Scientist, you will use data to solve business problems. The Delivery Problem course will help you learn how to apply data science techniques to optimize delivery routes and improve customer service. This course will also help you develop the skills you need to communicate your findings to decision-makers.

See salaries and explore the career path for Data Scientist

Supply Chain Manager

As a Supply Chain Manager, you will be responsible for managing the flow of goods and materials throughout a supply chain. The Delivery Problem course will help you learn how to optimize supply chains and minimize inventory costs. This course will also help you develop the skills you need to manage relationships with suppliers and customers.

See salaries and explore the career path for Supply Chain Manager

Transportation Planner

As a Transportation Planner, you will be responsible for planning and managing transportation systems. The Delivery Problem course will help you learn how to design efficient transportation networks and minimize traffic congestion. This course will also help you develop the skills you need to work with stakeholders and community groups.

See salaries and explore the career path for Transportation Planner

Logistics Analyst

As a Logistics Analyst, you will be responsible for planning and managing the movement of goods and materials. The Delivery Problem course will help you learn how to design efficient supply chains and minimize transportation costs. This course will also help you develop the skills you need to analyze data and make informed decisions.

See salaries and explore the career path for Logistics Analyst

Management Consultant

As a Management Consultant, you will help businesses solve problems and improve their performance. The Delivery Problem course will help you learn how to apply analytical techniques to identify and solve business problems. This course will also help you develop the skills you need to communicate your findings to decision-makers.

See salaries and explore the career path for Management Consultant

Actuary

As an Actuary, you will use mathematical and statistical techniques to assess risk and uncertainty. The Delivery Problem course will help you learn how to apply mathematical and analytical techniques to real-world problems. This course will also help you develop the skills you need to work in a team environment and deliver high-quality work products.

See salaries and explore the career path for Actuary

Financial Analyst

As a Financial Analyst, you will be responsible for analyzing financial data and making investment recommendations. The Delivery Problem course will help you learn how to apply mathematical and analytical techniques to financial data. This course will also help you develop the skills you need to communicate your findings to decision-makers.

See salaries and explore the career path for Financial Analyst

Delivery Driver

As a Delivery Driver, you will be responsible for transporting goods and packages to customers. The Delivery Problem course will help you learn how to optimize your routes and deliver goods efficiently. This course will also help you develop the skills you need to provide excellent customer service.

See salaries and explore the career path for Delivery Driver