The traveling salesman problem with release dates and
pptx
keyboard_arrow_up
School
Ohio State University *
*We aren’t endorsed by this school
Course
822
Subject
Industrial Engineering
Date
Dec 6, 2023
Type
pptx
Pages
16
Uploaded by ChancellorFrogPerson887
The traveling salesman problem with release dates and drone resupply
Presented By: Aaron Fernandes
Paper By: Juan C. Pina-Pardo, Daniel F. Silva, Alice E. Smith
12/02/2023
2
Overview
•
Introduction
•
Literature Review
•
Problem Description
•
Methodology •
Results
12/02/2023
3
Introduction
The burgeoning customer demand for rapid delivery, including next-day or 2-day shipping, has surged in recent years (World Economic Forum, 2020).
This trend demands streamlined last-mile logistics, where operators juggle route planning and immediate incoming requests, striving for same-day delivery from local facilities.
This problem was originally addressed by the Traveling Salesman Problem(TSP), which involved developing an optimal solution only involving a truck to deliver the packages.
This paper explores a solution involving drones sending new orders to delivery vehicles mid-route, eliminating the need for vehicles to return to the depot. We analyze this approach's advantages compared to the traditional method, ensuring a fair comparison by assuming full knowledge of order details for both strategies.
Your preview ends here
Eager to read complete document? Join bartleby learn and gain access to the full version
- Access to all documents
- Unlimited textbook solutions
- 24/7 expert homework help
12/02/2023
4
Archetti et al. (2015, 2018), introduced the TSPRD with the objective being minimizing waiting time.
Shelbourne et al. (2017) furthered this concept by also addressing the capacitated VRP.
Reyes et al. (2018) extended Archetti’s work by addressing routing complexities with release dates and deadlines along the same road.
Klapp et al. (2016, 2018) focused on Same-Day Delivery (SDD) services, studying dispatch problems using Markov Decision Process (MDP) models for single-truck scenarios. Their later work proposed MILP formulations for deterministic scenarios in network graphs and discussed heuristics for stochastic versions.
Literature Review
Optimize the delivery of orders to customers with release dates using a truck and a drone for resupply.
Goal: Minimize the time to deliver all orders while respecting the release dates of the orders and the endurance of the drone.
Assumptions: •
Each customer can order only once per day
•
Known release dates for orders at the planning outset
•
Loading orders onto the truck at the depot or via the drone during the route
•
The drone meeting the truck only at customer locations with associated unloading and launching times
•
No return trips for the truck to the depot
•
Drone to return to the depot before resupplying the truck again
12/02/2023
5
Problem Description
12/02/2023
6
First Drone Resupply Operation VS Optimal TSPRD-DR Solution
Your preview ends here
Eager to read complete document? Join bartleby learn and gain access to the full version
- Access to all documents
- Unlimited textbook solutions
- 24/7 expert homework help
12/02/2023
8
Decomposition Approach
Solution approach for solving larger instances of customers.
We break the problem into 2 stages:
•
Truck Routing Decisions •
Drone Resupply Decisions
12/02/2023
9
Routing decisions
Drone-resupply decisions
Your preview ends here
Eager to read complete document? Join bartleby learn and gain access to the full version
- Access to all documents
- Unlimited textbook solutions
- 24/7 expert homework help
12/02/2023
10
Results
•
From our computational MILP model, we achieved a 20% reduction in total delivery time compared to the traditional TSP problem using trucks only.
•
Decomposition Approach Results:
•
Over the instances of 10 customers, experiments showed that this approach obtained 13 of 24 optimal solutions in less than one second on average.
•
For instances of 15 customers, 12 of 19 optimal solutions were found in less than 2 min on average
04
What’s next
Monthly timeline
Jul
Aug
Sep
Nov
Oct
Dec
Jan
Feb
Mar
Apr
May
Jun
Product launch
Lorem ipsum dolor sit amet, consectetur adipiscing elit. Mauris vitae lorem id leo accumsan.
Product launch
Lorem ipsum dolor sit amet, consectetur adipiscing elit. Mauris vitae lorem id leo accumsan.
Product launch
Lorem ipsum dolor sit amet, consectetur adipiscing elit. Mauris vitae lorem id leo accumsan.
Product launch
Lorem ipsum dolor sit amet, consectetur adipiscing elit. Mauris vitae lorem id leo accumsan.
Q1
Q2
Q3
Q4
12/02/2023
12
Your preview ends here
Eager to read complete document? Join bartleby learn and gain access to the full version
- Access to all documents
- Unlimited textbook solutions
- 24/7 expert homework help
Goals for Q1
Employee opportunities
•
End of fiscal celebration on July 15
th
•
Employee day of learning on August 14
th •
Employee Yoga on September 3
rd
•
Seminar series begins September 10
th
Business priorities
•
Increase customer satisfaction by 2%
•
Maintain growth
•
Initiative partnership with 3
rd
party organizations
12/02/2023
13
Goals for Q2
Business priorities
•
Increase customer satisfaction by 2%
•
Maintain growth
Added priorities
•
Improve our social media presence
•
Ensure the cost of development stays below budget
Employee opportunities
•
Interns begin
•
Indoor rec leagues
•
Chess tournaments
•
Big Game watching party
12/02/2023
14
Summary
Our business is good
Profits are up in the last quarter by 3%
Our customers keep coming back
We increased customer retention by 4%
We’re getting our work done
We finished the consolidation project
We’re leaders
We are top leaders in the industry across the board
We’re delivering for our customers
Customer satisfaction increased from 70 to 80%
Our team is growing
We welcomed 3 new team members last quarter
12/02/2023
15
Your preview ends here
Eager to read complete document? Join bartleby learn and gain access to the full version
- Access to all documents
- Unlimited textbook solutions
- 24/7 expert homework help
05
Closing
Thanks to your commitment and strong work ethic, we know next year will be even better than the last. We look forward to working together. Ana
sales@contoso.com
12/02/2023
16