%Version 3.1 December 2024
% See section 11 of the User Manual for version history
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%                                                                 %%
%% Please do not use \input{...} to include other tex files.       %%
%% Submit your LaTeX manuscript as one .tex document.              %%
%%                                                                 %%
%% All additional figures and files should be attached             %%
%% separately and not embedded in the \TeX\ document itself.       %%
%%                                                                 %%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%\documentclass[referee,sn-basic]{sn-jnl}% referee option is meant for double line spacing

%%=======================================================%%
%% to print line numbers in the margin use lineno option %%
%%=======================================================%%

%%\documentclass[lineno,pdflatex,sn-basic]{sn-jnl}% Basic Springer Nature Reference Style/Chemistry Reference Style

%%=========================================================================================%%
%% the documentclass is set to pdflatex as default. You can delete it if not appropriate.  %%
%%=========================================================================================%%

%%\documentclass[sn-basic]{sn-jnl}% Basic Springer Nature Reference Style/Chemistry Reference Style

%%Note: the following reference styles support Namedate and Numbered referencing. By default the style follows the most common style. To switch between the options you can add or remove Numbered in the optional parenthesis. 
%%The option is available for: sn-basic.bst, sn-chicago.bst%  
 
%%\documentclass[pdflatex,sn-nature]{sn-jnl}% Style for submissions to Nature Portfolio journals
%%\documentclass[pdflatex,sn-basic]{sn-jnl}% Basic Springer Nature Reference Style/Chemistry Reference Style
\documentclass[pdflatex,sn-mathphys-num]{sn-jnl}% Math and Physical Sciences Numbered Reference Style
%%\documentclass[pdflatex,sn-mathphys-ay]{sn-jnl}% Math and Physical Sciences Author Year Reference Style
%%\documentclass[pdflatex,sn-aps]{sn-jnl}% American Physical Society (APS) Reference Style
%%\documentclass[pdflatex,sn-vancouver-num]{sn-jnl}% Vancouver Numbered Reference Style
%%\documentclass[pdflatex,sn-vancouver-ay]{sn-jnl}% Vancouver Author Year Reference Style
%%\documentclass[pdflatex,sn-apa]{sn-jnl}% APA Reference Style
%%\documentclass[pdflatex,sn-chicago]{sn-jnl}% Chicago-based Humanities Reference Style

%%%% Standard Packages
%%<additional latex packages if required can be included here>
%\documentclass{article}
\documentclass[sn-basic]
\usepackage{graphicx}%
\usepackage{multirow}%
\usepackage{amsmath,amssymb,amsfonts}%
\usepackage{amsthm}%
\usepackage{mathrsfs}%
\usepackage[title]{appendix}%
\usepackage{xcolor}%
\usepackage{textcomp}%
\usepackage{manyfoot}%
\usepackage{booktabs}%
\usepackage{algorithm}%
\usepackage{algorithmicx}%
\usepackage{algpseudocode}%
\usepackage{listings}%

\usepackage{graphicx}
\usepackage{subcaption}
\usepackage[margin=1in]{geometry}
%%%%

\newcommand{\tred}{\textcolor{red}}
\newcommand{\tblue}{\textcolor{blue}}

%%%%%=============================================================================%%%%
%%%%  Remarks: This template is provided to aid authors with the preparation
%%%%  of original research articles intended for submission to journals published 
%%%%  by Springer Nature. The guidance has been prepared in partnership with 
%%%%  production teams to conform to Springer Nature technical requirements. 
%%%%  Editorial and presentation requirements differ among journal portfolios and 
%%%%  research disciplines. You may find sections in this template are irrelevant 
%%%%  to your work and are empowered to omit any such section if allowed by the 
%%%%  journal you intend to submit to. The submission guidelines and policies 
%%%%  of the journal take precedence. A detailed User Manual is available in the 
%%%%  template package for technical guidance.
%%%%%=============================================================================%%%%

%% as per the requirement new theorem styles can be included as shown below
\theoremstyle{thmstyleone}%
\newtheorem{theorem}{Theorem}%  meant for continuous numbers
%%\newtheorem{theorem}{Theorem}[section]% meant for sectionwise numbers
%% optional argument [theorem] produces theorem numbering sequence instead of independent numbers for Proposition
\newtheorem{proposition}[theorem]{Proposition}% 
%%\newtheorem{proposition}{Proposition}% to get separate numbers for theorem and proposition etc.

\theoremstyle{thmstyletwo}%
\newtheorem{example}{Example}%
\newtheorem{remark}{Remark}%
%\newcommand{\tred}{\textcolor{red}}

\theoremstyle{thmstylethree}%
\newtheorem{definition}{Definition}%

\raggedbottom
%%\unnumbered% uncomment this for unnumbered level heads

\begin{document}

\title[Article Title]{A Corridor-Based Drone-Carrier Vehicle System for Environment-Aware Last-Mile Delivery}

%%=============================================================%%
%% GivenName	-> \fnm{Joergen W.}
%% Particle	-> \spfx{van der} -> surname prefix
%% FamilyName	-> \sur{Ploeg}
%% Suffix	-> \sfx{IV}
%% \author*[1,2]{\fnm{Joergen W.} \spfx{van der} \sur{Ploeg} 
%%  \sfx{IV}}\email{iauthor@gmail.com}
%%=============================================================%%

\author*[1]{\fnm{Falak} \sur{Fatima}}\email{falakfatima@iisc.ac.in}

\author[2]{\fnm{P.B.} \sur{Sujit}}\email{sujit@iiserb.ac.in}

\author[3]{\fnm{Debasish} \sur{Ghose}}\email{dghose@iisc.ac.in}
% \equalcont{These authors contributed equally to this work.}

\affil[1]{\orgdiv{Robert Bosch Centre for Cyber Physical Systems}, \orgname{Indian Institute of Science}, \city{Bangalore}, \postcode{560012}, \state{KA}, \country{India}}
\affil[2]{\orgiv{EECS Department}, \orgname {Indian Institute of Science Education and Research}, \city{Bhopal}, \postcode {462001} \state{Madhya Pradesh}, \country{India}}
\affil[3]{\orgdiv{RBCCPS and Department of Aerospace Engineering}, \orgname {Indian Institute of Science}, \city{Bangalore}, \postcode{560012}, \state{KA}, \country{India}}



\abstract
{This paper proposes a corridor-based drone–carrier framework for last-mile urban delivery that explicitly minimizes environmental impact while improving logistics efficiency. Starting from a central warehouse, customer locations are first partitioned into clusters using the k-means algorithm, and a carrier vehicle transports multiple drones—each loaded with up to a specified number of packages and equipped with on-board charging—and sequentially pauses at optimized “corridor entrance” points. At each entrance, a drone departs along a corridor toward its assigned customer cluster. By confining drone trajectories within narrow corridors instead of allowing  point-to-point flights, noise dispersion and ecological disturbances are substantially reduced, and airspace congestion is minimized. Within each cluster, the drone applies a nearest-neighbor heuristic followed by a refinement strategy to sequence deliveries, ensuring that battery endurance and payload constraints are respected. After completing its sortie, the drone returns along the same corridor to rendezvous with the moving carrier; if necessary, it may hover until the vehicle arrives. In alternative scenarios, temporary depot stations located near corridor entrances support battery recharging and package replenishment—thus avoiding unnecessary drone hovering and eliminating unnecessary carrier vehicle movement—further extending the operational range without detours into densely populated areas. Simulation results in realistic urban layouts demonstrate that this strategy not only lowers total travel distance and delivery times compared to conventional point-to-point approaches but also confines noise and emissions to narrow aerial corridors, thereby fostering sustainable, community-friendly drone logistics.}
% \tred{Needs rewriting to talk about sustainability/environment awareness.}}

\keywords{Hybrid drone–carrier architecture, Cluster-based assignment, Optimal pickup-point, corridor design, Coordinated carrier–drone synchronization, Traveling salesman problem}

\maketitle

\section{Introduction}\label{sec1}

The rapid expansion of e-commerce has placed unprecedented demands on urban logistics: customers expect ever faster, cheaper, and more sustainable deliveries, yet dense street networks, traffic congestion, and strict environmental regulations hinder traditional delivery vans. In fact, last-mile operations can account for over 53\% of total shipping costs and contribute significantly to urban emissions and roadway congestion as reported in \cite{accenture2020} and \cite{wef2024}.
Unmanned aerial vehicles (UAVs), or drones, offer a promising solution by flying above ground‐level traffic and directly serving dispersed customer locations. However, pure drone delivery is constrained by limited payload capacity, battery endurance, and regulatory flight restrictions \cite{MurrayChu2015, DorlingMessierMagierowski2016}. Conversely, truck‐only schemes remain reliable but suffer inefficiencies in low‐density or highly congested areas \cite{AgatzBoumanSchmidt2018}. To bridge this gap, hybrid drone–truck frameworks have emerged: a ground vehicle carries and recharges drones, deploying them at carefully chosen rendezvous points for last‐mile service \cite{Sheu2017, PoikonenGoldenWasil2020}.
% \tblue{}
However, a drone delivery system is often designed on a point-to-point delivery strategy which does not take into account the effect on the environment caused by the spread of  drone paths in the available airspace, in terms of noise pollution, ecological damage, etc. In our work, we propose a corridor-based last-mile delivery system in a drone-carried vehicle combined operation that causes minimal environmental impact. As an illustration, see Fig.\ref{fig:point_to_point_delivery} shows a drone delivery network where the drone paths are spread in the airspace to occupy a large volume of space as against a corridor-based system in Fig.\ref{fig:Corridor-based last-mile delivery strategy} where the drones are confined to a constrained airspace for most of their delivery path.  

 
% \tred{I will send this figure to you later.}

% In the literature, several studies have explored aspects of this hybrid model. Murray and Chu \cite{MurrayChu2015} introduced the Flying Sidekick TSP for a single truck–single drone setup, and Agatz et al. \cite{AgatzBoumanSchmidt2018} extended it to multiple sorties. Dorling et al. \cite{DorlingMessierMagierowski2016} and Sheu et al. \cite{Sheu2017} examined energy-aware routing with mid-mission recharging, while Poikonen et al. \cite{PoikonenGoldenWasil2020} and Wang et al. \cite{WangEtAl2017} developed formulations for multiple drones per vehicle. Cluster-first, route-second heuristics have been proposed by Ferrández et al. \cite{FerrandezEtAl2015} and Xu et al.  \cite{XuEtAl2021}, and the concept of airspace “corridors” or sky highways was introduced by Frazzoli et al.  \cite{FrazzoliEtAl2015} and adapted for urban grids by Kim and Shin \cite{KimShin2019}. \tred{Talk about and cite geofenced corridors from our group}. \tred{Not clear what is meant by the next sentence} Foundational partitioning techniques by Golden and Assad \cite{GoldenAssad1988} and multi-agent coordination frameworks by Tsourdos et al.\ \cite{Tsourdos2016} provide useful baselines. Despite this progress, few approaches account simultaneously for realistic city-block geometries, concurrent multi-drone sorties, and integrated depot-station resupply—a gap we aim to fill.

% \tred{UP TO THIS}
In the literature, several studies have explored aspects of hybrid drone–truck routing. Murray and Chu \cite{MurrayChu2015} introduced the Flying Sidekick TSP for a single truck–single drone setup, and Agatz et al. \cite{AgatzBoumanSchmidt2018} extended it to multiple sorties. Dorling et al. \cite{DorlingMessierMagierowski2016} and Sheu et al. \cite{Sheu2017} examined energy-aware routing with mid-mission recharging, while Poikonen et al. \cite{PoikonenGoldenWasil2020} and Wang et al. \cite{WangEtAl2017} developed formulations for multiple drones per vehicle. Cluster‐first, route‐second heuristics have been proposed by Ferrández et al. \cite{FerrandezEtAl2015} and Xu et al. \cite{XuEtAl2021}. The concept of airspace “corridors” or sky highways was first introduced by Frazzoli et al. \cite{FrazzoliEtAl2015} and later adapted for urban‐grid planning by Kim and Shin \cite{KimShin2019}. Building on this, Tony et al. \cite{TonyRatnooGhose2021} proposed adaptive geofenced corridors in the CORRIDRONE architecture to guarantee safe, no‐fly‐zone compliance in dense city‐block environments. Golden and Assad \cite{GoldenAssad1988} introduced classic vehicle‐routing partitioning methods that can be adapted to cluster assignment in hybrid logistics, while Tsourdos et al. \cite{Tsourdos2016} developed distributed multi‐agent coordination algorithms for UAV networks, providing a basis for scheduling and communication among multiple drones. 

In this paper, we propose a corridor‐style, cluster‐based hybrid delivery framework that partitions customer locations using k‐means++; computes a corridor—from each drone’s precomputed optimal pickup point on the carrier’s route to its cluster centroid—that can follow non‐linear paths constrained by urban geometry; and sequences intra‐cluster deliveries via a nearest‐neighbor heuristic refined with 2‐OPT. By confining drones to these narrow corridors instead of point‐to‐point routes, environmental disturbances such as noise pollution and ecological impact are significantly reduced (see Fig.\ref{fig:point_to_point_delivery} vs. Fig. \ref{fig:Corridor-based last-mile delivery strategy}). Temporary depot stations at pickup points—stocked with packages and charging facilities—eliminate drone hovering or waiting times and prevent unnecessary carrier returns to the warehouse. We also develop an end‐to‐end simulation that incorporates battery constraints, depot‐station resupply, and carrier–drone synchronization across multiple drones, and we demonstrate significant reductions in total travel distance and delivery time compared to existing hybrid methods.

The remainder of this paper is organized as follows. Section \ref{sec2} defines the problem statement. Section \ref{sec3} formulates the problem in detail and describes our clustering, pickup point selection, and corridor generation algorithms. Section \ref{sec4} presents our solution methodology for each operational scenario. Section \ref{sec5} details the simulation setup and discusses the results, and Section \ref{sec6} concludes with key insights and directions for future research.

\section{Problem Statement}\label{sec2}
A hybrid drone–carrier delivery system is studied in which a ground vehicle transports packages from a warehouse and serves as a mobile base for multiple drones to launch at their respective optimal pickup locations .In initial scenarios along its route, the carrier provides in-route battery recharging and package resupply, enabling drones to perform several sorties without returning to the warehouse. Later, once the carrier has launched all drones, a temporary depot station is established at the optimal pickup location to handle package replenishment and recharging. We denote the drone’s constant flight speed by \(v_{d}\) and the carrier’s constant driving speed by \(v_{c}\), and define their speed ratio as
\begin{equation}\label{eq:speed ratio}
  \rho = \frac{v_{d}}{v_{c}}.
\end{equation}

\begin{figure}[!htb]
  \centering
  \begin{subfigure}[b]{0.45\textwidth}
    \includegraphics[width=\textwidth]{figures/point_to_point_del.png}
    \caption{Point-to-point delivery strategy}
    \label{fig:point_to_point_delivery}
  \end{subfigure}
  \hfill
  \begin{subfigure}[b]{0.45\textwidth}
    \includegraphics[width=\textwidth]{figures/corridor_delivery.png}
    \caption{Corridor-based last-mile delivery strategy}
    \label{fig:Corridor-based last-mile delivery strategy}
  \end{subfigure}
  \caption{Depicts the overview of the problem statement}
  \label{fig:singlecluster_results}
\end{figure}
The assumption of constant speed is not realistic as the speeds may fluctuate due to various reasons. However, in this scenario, we can consider them to be the average speeds of the drone and the carrier vehicle. 

Our key decision is to select, for each drone, an \emph{optimal pickup point} on the carrier’s route that minimizes total drone flight distance (or time) for serving assigned customers.  Customers are located off the carrier’s route: given $N$ customer locations $\{x_i\}_{i=1}^N$, we partition them into $K$ clusters, and assign one drone per cluster.
At its launch point, each drone follows a \emph{corridor} to the cluster centroid, then leaves the corridor to visit individual customers.  Within each cluster, delivery sequencing is determined by a nearest-neighbor heuristic followed by 2-OPT refinement.
We analyze a few operational scenarios given below:
\begin{enumerate}
  \item[]\textbf{Scenario 1: Single‑cluster, single‑drone with corridor}  A single cluster of customers is served by one drone; the drone flies along a corridor from the optimal pickup point to the cluster centroid before making deliveries.
  \item[]\textbf{Scenario 2: Multi‑cluster, multi‑drone with corridors}  Each of $K$ clusters defines a corresponding corridor; drones launch from their optimal points, follow their corridors to centroids, then execute cluster tours. Drones carry up to four packages per sortie; after serving up to four customers, the drone returns along the same corridor to rendezvous with the carrier.  If the carrier has already passed the pickup point, the drone hovers until the next encounter.
  \item[]\textbf{Scenario 3: Temporary depot stations}  At each optimal pickup point, the carrier drops a temporary depot stocked with packages and charging facilities. Drones can return to these depots for recharging and resupply, while the carrier returns to the warehouse. Temporary depot stations prevent drone hovering time.
\end{enumerate}
The joint decision variables to be optimized include cluster assignments, pickup‐point locations along the carrier’s path, corridor geometries, intra‐cluster routing sequences, and carrier–drone synchronization rules. Together, these variables define a corridor‐based last‐mile delivery system in which a drone‐carried vehicle operates with minimal environmental impact. All decisions must respect drone payload limits and battery endurance while minimizing total drone flight distance and overall mission completion time.


\section{Problem Formulation}\label{sec3}
We now present the mathematical formulations of the scenario discussed in Section \ref{sec2}.
The following assumptions will be used throughout the paper.\\

\noindent\textbf{Assumptions}
\begin{enumerate}
    \item All vehicles (drone and carrier) travel at constant speeds throughout their operations.
    \item Corridors are modeled as straight‐line segments that approximate possible urban geometry in the simulation.
\end{enumerate}

% \textbf{Assumptions}: Considered a constant speed model for the drone and carrier vehicle.
\subsection{Single drone, single corridor}\label{sec:sdsc_math}

Consider the scenario shown in Fig.\ref{fig:diagram_single_customer}, where $\mathcal{C} = \{c_i = (x_i,y_i)\mid i=1,\dots,N\}$ is the set of $N$ customer locations. The carrier moves along a fixed closed path of total length $L_{\rm total}$, parameterized by arc‐length $s\in[0,L_{\rm total}]$, with position
$P(s) = \texttt{point\_at\_arc\_length}(s)\in\mathbb{R}^2$. The drone flies at a constant speed $v_d$, carries at most $Q$ packages per sortie, and has battery endurance $B$ (in distance units). The carrier’s constant speed is $v_c$.
\begin{figure}[h]
    \centering
    \includegraphics[width=0.75\linewidth]{figures/single-corridor.png}
    \caption{Schematic diagram of Single-cluster, single-drone with corridor }
    \label{fig:diagram_single_customer}
\end{figure}
We seek a launch point $s_0\in[0,L_{\rm total}]$ that maximizes the number of customers served and, secondarily, minimizes total drone distance and flight time. For any $s_0$, let
$N_{\rm served}(s_0)$ be the total number of customers reachable by sorties launched at $s_0$ within battery and payload limits; let
$D_d(s_0) = \sum_{\text{sorties}}(\text{flight distance} + \text{hover distance})$
be the aggregate distance flown (including hovering) by all drones launched from $s_0$; and let
$T_d(s_0) = D_d(s_0)/v_d$
be the corresponding total flight time, where $v_d$ is the drone’s constant speed.

We adopt the lexicographic objective
\begin{equation}\label{eq:single_corridor_objective}
  \max_{s_0}\;\Bigl(N_{\rm served}(s_0),\;-D_d(s_0),\;-T_d(s_0)\Bigr),
\end{equation}
subject to the following constraints for each sortie $k$ launched from $P(s_0)$:  
\begin{equation}\label{eq:constraints_1}
  2\lVert P(s_0)-\mathrm{centroid}_k\rVert + d_{\rm tsp}^k \le B,\quad k=1,\dots,K
\end{equation}
\begin{equation}\label{eq:constraint_2}
  \#\{\mathrm{services\ in\ sortie}\ k\} \le Q,\quad k=1,\dots,K
\end{equation}
\begin{equation}\label{eq:constraint_3}
  \Delta s_k = \frac{2\,\lVert P(s_0)-\mathrm{centroid}_k\rVert + d_{\rm tsp}^k}{p},\quad k=1,\dots,K,\quad
  0 \le s_0 \le L_{\rm total}.
\end{equation}

 \noindent Here, constraint \eqref{eq:constraints_1} ensures that each sortie—comprising the corridor segment plus the intra‐cluster tour 
does not exceed the drone’s battery endurance. Constraint \eqref{eq:constraint_2} enforces the payload capacity per sortie. Finally, constraint \eqref{eq:constraint_3} synchronizes drone and carrier movements using the speed ratio \(p = v_d / v_c\) and bounds the launch point along the carrier’s route. In these expressions, \(\mathrm{centroid}_k\) denotes the centroid of cluster \(k\), and \(d_{\rm tsp}^{k}\) is the length of the intra‐cluster tour (nearest‐neighbor + 2-OPT) for sortie \(k\).  

\end{itemize}
\subsection{Multiple drones-multiple corridors}
\begin{figure}[h]
    \centering
    \includegraphics[width=0.75\linewidth]{figures/multi_corridor.png}
    \caption{Schematic diagram of scenario~2: multi‑cluster, multi‑drone with corridors}
    \label{fig:multi_corridor}
\end{figure}
\noindent
Consider the scenario illustrated in Fig.~\ref{fig:multi_corridor}. We partition the customer set into \(K\) clusters via \(k\)-means. Let each customer location \(x_i\in\mathbb{R}^2\) be assigned a label \(\ell_i\in\{1,\dots,K\}\), and define
\begin{equation}\label{eq:cluster_eq}
  C_k = \{\,x_i : \ell_i = k\}, 
  \quad
  c_k = \frac{1}{|C_k|}\sum_{x\in C_k}x,
\end{equation}
where \(C_k\) is the set of customers in cluster \(k\) and \(c_k\) its centroid.
Within cluster \(k\), the drone visits each \(x\in C_k\) exactly once. Denote the minimal tour length by
\begin{equation}\label{eq:tsp}
  \mathrm{TSP}(C_k)
  = \min_{\pi\in\Pi_k}
    \Bigl\|c_k - x_{\pi(1)}\Bigr\|
  + \sum_{j=1}^{|C_k|-1}\bigl\|x_{\pi(j)}-x_{\pi(j+1)}\bigr\|
  + \bigl\|x_{\pi(|C_k|)}-c_k\bigr\|,
\end{equation}
where \(\Pi_k\) is the set of all permutations of the indices in \(C_k\).
A sortie consists of straight “out” and “back” legs from the carrier path to \(c_k\). If the launch point corresponds to arc‐length \(s_k\) on the carrier route, each corridor leg has length
\begin{equation}\label{eq:corridor_dist}
  D_{\mathrm{corr}}(s_k)
  = \bigl\lVert P(s_k) - c_k\bigr\rVert,
\end{equation}
so the round‐trip corridor distance is \(2\,D_{\mathrm{corr}}(s_k)\). The total flight distance for drone \(k\) launching at \(s_k\) is
\begin{equation}\label{eq:total_dist}
  D_k(s_k)
  = 2\,D_{\mathrm{corr}}(s_k) + \mathrm{TSP}(C_k).
\end{equation}
Feasibility requires
\begin{equation}\label{eq:battery}
  D_k(s_k) \le B,\quad k=1,\dots,K.
\end{equation}
We then choose launch positions \(\{s_k\}_{k=1}^K\) to minimize the total flight distance:
\begin{subequations}\label{eq:multi_opt}
\begin{align}
  & \underset{s_1,\dots,s_K\in[0,L_{\rm total}]}{\text{minimize}}
  && \sum_{k=1}^K D_k(s_k),\\
  & \text{subject to}
  && D_k(s_k) \le B,\quad k=1,\dots,K.
\end{align}
\end{subequations}

\subsection{Multi drone-multi corridor with temporary depot station}
\begin{figure}[h]
    \centering
   \includegraphics[width=0.75\linewidth]{figures/depot_station.png}
    \caption{Schematic diagram of scenario: Multi cluster-multi corridor with temporary depot station}
    \label{fig:depot station}
\end{figure}

\noindent
Consider the scenario depicted in Fig.~\ref{fig:depot station}. We partition the $N$ customer locations into $K$ clusters via $k$-means; let $C_k$ denote the set of points in cluster $k$. With a per‑drone payload capacity of $Q$, cluster $k$ requires
\[
  n_k = \Bigl\lceil\tfrac{|C_k|}{Q}\Bigr\rceil,\quad
  C_k = \bigsqcup_{j=1}^{n_k} C_k^j,\quad
  |C_k^j|\le Q.
\]
For each cluster $k$, the carrier drops a temporary depot station at arc‑length $s_k$ on its route; drones launch from and return to this depot, avoiding any hovering. Denoting the cluster centroid by
$c_k = \tfrac{1}{|C_k|}\sum_{x\in C_k} x,$
the one‑way corridor distance from depot to centroid is
$D_{\rm corr}(s_k) = \lVert P(s_k) - c_k\rVert.$
The flight distance of the $j$th sortie for cluster $k$ is
\begin{equation}\label{eq:sortie_flight}
  D_k^j(s_k)
  = 2\,D_{\rm corr}(s_k)
    + \mathrm{TSP}(C_k^j),
\end{equation}
where $\mathrm{TSP}(C_k^j)$ is defined in \eqref{eq:tsp}. Feasibility requires
\begin{equation}\label{eq:depot_feasibility}
  D_k^j(s_k)\le B,\quad j=1,\dots,n_k.
\end{equation}
We then choose depot locations $\{s_k\}_{k=1}^K$ to minimize total flight distance:
\begin{subequations}
\begin{align}
  \underset{s_1,\dots,s_K\in[0,L_{\rm total}]}{\mathrm{minimize}}\quad
  & \sum_{k=1}^K\sum_{j=1}^{n_k}
      \bigl(2\,D_{\rm corr}(s_k) + \mathrm{TSP}(C_k^j)\bigr),\\
  \mathrm{subject\ to}\quad
  & D_k^j(s_k)\le B,
    \quad j=1,\dots,n_k,\;k=1,\dots,K.
\end{align}

\section{Methodology}\label{sec4}
In this section, we present a comprehensive description of the delivery scenarios introduced in Section~\ref{sec2} and the corresponding algorithmic solutions. For each scenario, single‐corridor, multi‐corridor, and multi‐corridor with temporary depots, we detail the key steps: customer clustering (k-means++), corridor construction, intra-cluster TSP routing (nearest-neighbor + 2-OPT), and feasibility checks for battery and payload constraints.

\begin{algorithm}
\caption{Launch‐Point Optimization and Delivery Planning for multi corridor setup}
\label{alg:joint}
\begin{algorithmic}[1]
\Require Customer set $\mathcal{C}$, carrier path length $L_{\mathrm{total}}$, carrier speed $v_c$, drone speed $v_d$, payload limit $Q$, battery endurance $B$, sweep grid size $N_{\mathrm{sweep}}$
\State Partition $\mathcal{C}$ into clusters $\{C_k\}_{k=1}^M$ via k-means++
\State Compute cluster centroids $\mathrm{centroid}_k \gets \frac{1}{|C_k|}\sum_{c\in C_k}c$ for $k=1,\dots,M$
\State Initialize best metrics: 
\[
\textit{best} \gets (\mathrm{served}=-\infty,\;\mathrm{dist}=+\infty,\;\mathrm{time}=+\infty,\;s_0^*=\bot)
\]upper vb
\For{$s_0$ in \texttt{linspace}(0, $L_{\mathrm{total}}$, $N_{\mathrm{sweep}}$)}  
  \State $P_0 \gets \texttt{point\_at\_arc\_length}(s_0)$  
  \State $\mathrm{served}\gets 0,\;D_d\gets 0,\;T_d\gets 0$  
  \For{$k=1$ to $M$}  
    \State \Comment{Define corridor and intra-cluster tour}
    \State $d_{\rm corr}\gets \|P_0 - \mathrm{centroid}_k\|$  
    \If{$2\,d_{\rm corr} > B$} \Comment{cannot even reach centroid} \textbf{continue} \EndIf  
    \State $R_k \gets \Call{NearestNeighbor}{C_k,\;\text{start}=\mathrm{centroid}_k}$  
    \State $R_k \gets \Call{TwoOpt}{R_k}$  
    \State $R_k \gets R_k[:\min(Q,|R_k|)]$  
    \State $d_{\rm tsp}\gets \mathrm{length}(R_k)$  
    \If{$2\,d_{\rm corr} + d_{\rm tsp} > B$} \Comment{battery infeasible} \textbf{continue} \EndIf  
    \State \Comment{Accumulate metrics for this sortie}
    \State $\mathrm{served}\;+\!=\;|R_k|$  
    \State $D_d\;+\!=\;2\,d_{\rm corr} + d_{\rm tsp}$  
    \State $T_d\;+\!=\;(2\,d_{\rm corr} + d_{\rm tsp})/v_d$  
  \EndFor  
  \State \Comment{Lexicographic comparison: maximize served, then minimize distance, then time}
  \If{  
    $\mathrm{served} > \textit{best.served}$ \textbf{or}  
    ($\mathrm{served} = \textit{best.served}$ \textbf{and} $D_d < \textit{best.dist}$) \textbf{or}  
    ($\mathrm{served} = \textit{best.served}$ \textbf{and} $D_d = \textit{best.dist}$ \textbf{and} $T_d < \textit{best.time}$)  
  }
    \State $\textit{best} \gets (\mathrm{served},\,D_d,\,T_d,\,s_0)$  
  \EndIf  
\EndFor  
\State \Return Optimal launch point $s_0^* = \textit{best}.s_0$ with metrics  
\[
N_{\mathrm{served}} = \textit{best.served},\quad
D_d = \textit{best.dist},\quad
T_d = \textit{best.time}
\]
\end{algorithmic}
\end{algorithm}

Algorithm \ref{alg:joint} addresses the  problem of launch‐point optimization and delivery planning for a multi corridor setup. Here, the algorithm first groups nearby customers by proximity in Scenario 1 (no k-means); in later scenarios, it applies k-means++ with the hinge method to form $K$ clusters. It then uniformly sweeps launch points $s_0\in[0,L_{\rm total}]$ along the carrier route. For each $s_0$, it computes the carrier location $P(s_0)$ and defines straight‐line corridors to each cluster centroid. From each centroid, a nearest‐neighbor tour refined by 2-OPT serves up to payload $Q$. If the round-trip distance—$2\times$corridor plus tour—does not exceed battery endurance $B$, the sortie is feasible and its served count, flight distance $D_d$, and flight time $T_d$ are recorded. After evaluating all clusters for that $s_0$, the algorithm stores the tuple $(N_{\rm served},D_d,T_d)$, repeats the sweep, and finally chooses the optimal launch point $s_0^*$ by lexicographically maximizing $N_{\rm served}$, then minimizing $D_d$, then $T_d\,$.  



Algorithm \ref{alg:depot_multi_corridor} addresses the problem of depot-enhanced launch-point optimization for multi-corridor, multi-
cluster Setup. Here, all drones are sent off at their respective optimal pickup points in a single pass of the carrier around its loop. Once every drone has launched, then at each cluster’s “best” launch point discrete set of temporary depot stations are assumed along the carrier route. These stations serve two critical functions.
\begin{enumerate}
    \item Package Replenishment. After a drone completes its first sortie, it can rendezvous at its assigned station to pick up fresh payloads and continue serving the remaining customers in its cluster without having to return all the way to the warehouse.
    \item Battery Recharge. If a drone’s remaining endurance is insufficient for another delivery, the depot station will provide service for recharging, allowing it to safely continue its tour.
\end{enumerate}

\begin{algorithm}[h]
\caption{Depot‐Enhanced Launch‐Point Optimization for Multi‐Corridor, Multi‐Cluster Setup}
\label{alg:depot_multi_corridor}
\begin{algorithmic}[1]
\Require 
  Customer set $\mathcal{C}$, 
  carrier path length $L_{\mathrm{total}}$, 
  carrier speed $v_c$, 
  drone speed $v_d$, 
  payload limit $Q$, 
  battery endurance $B$, 
  \State set of temporary depot stations 
  $\mathcal{S} = \{s_j\}_{j=1}^J$ 
  \Comment{arc‐length positions on the carrier path}
\State Partition $\mathcal{C}$ into clusters $\{C_k\}_{k=1}^M$ via k-means++
\State Compute cluster centroids 
  $\mathrm{centroid}_k \gets \frac{1}{|C_k|}\sum_{c\in C_k}c$
\For{$k=1$ to $M$}  
  \State initialize 
    $\textit{best}_k \gets (\mathrm{served}=-\infty,\;\mathrm{dist}=+\infty,\;\mathrm{time}=+\infty,\;s_k^*=\bot)$
  \For{each depot $s_j\in\mathcal{S}$}
    \State $P_j \gets \texttt{point\_at\_arc\_length}(s_j)$
    \State $d_{\rm corr}\gets \|P_j - \mathrm{centroid}_k\|$
    \If{$2\,d_{\rm corr} > B$} \Comment{can’t even reach centroid}
      \textbf{continue}
    \EndIf
    \State $R_k \gets \Call{NearestNeighbor}{C_k,\;\mathrm{start}=\mathrm{centroid}_k}$
    \State $R_k \gets \Call{TwoOpt}{R_k}$
    \State $R_k \gets R_k[:\min(Q,|R_k|)]$
    \State $d_{\rm tsp}\gets \mathrm{length}(R_k)$
    \If{$2\,d_{\rm corr} + d_{\rm tsp} > B$} \Comment{battery infeasible}
      \textbf{continue}
    \EndIf
    \State 
      $\mathrm{served}_j \gets |R_k|$,\quad
      $D_{d,j}\gets 2\,d_{\rm corr} + d_{\rm tsp}$,\quad
      $T_{d,j}\gets D_{d,j}/v_d$
    \If{lexico‐better$(\mathrm{served}_j,D_{d,j},T_{d,j})$ than \textit{best}$_k$}
      \State 
        $\textit{best}_k \gets (\mathrm{served}_j,D_{d,j},T_{d,j},s_j)$
    \EndIf
  \EndFor
\EndFor
\State \Return For each cluster $k$, its optimal depot 
  $s_k^*$ with 
  $N_{\mathrm{served},k},\,D_{d,k},\,T_{d,k}$ from $\textit{best}_k$.
\end{algorithmic}
\end{algorithm}

\clearpage

By pre‐placing these static depots at the computed optimal pickup points, we eliminate inefficient “hover‐and‐wait” periods where a drone would otherwise loiter near the carrier. Instead, the carrier simply follows its normal loop, and each drone—and only that drone—dives in and out of its depot station as needed. The result is a coordinated, low‐idle‐time delivery system that maximizes served customers while respecting both payload and battery constraints.
\section{Results and Discussion}\label{sec5}
\subsection{Single Cluster – Single Corridor}\label{sec:single_cluster}
We begin with all 12 closely spaced customers forming a single cluster.  The optimal launch point was found at 
$s_0 = -500.0$ which corresponds to the spatial coordinate \((0, 500)\) along the carrier route  as shown in figure \ref{fig:singlecluster_pickup} .  Using this pickup point as the “mouth” of the straight‐line corridor, the drone completes all deliveries in three sorties.  Intra‐cluster routing is performed with a nearest‐neighbor TSP heuristic followed by a 2-OPT refinement as provided in Figure \ref{fig:singlecluster_snapshot}.
\begin{figure}[h]
  \centering
  \begin{subfigure}[b]{0.4\textwidth}
    \includegraphics[width=\textwidth]{Results/singlecluster_pickup_point.png}
    \caption{Optimal pickup point for the single cluster}
    \label{fig:singlecluster_pickup}
  \end{subfigure}
  \hfill
  \begin{subfigure}[b]{0.42\textwidth}
    \includegraphics[width=\textwidth]{Results/singlecluster_snapshot.png}
    \caption{Animation snapshot of the single‐corridor delivery}
    \label{fig:singlecluster_snapshot}
  \end{subfigure}

  \caption{Results for the single‐cluster, single‐corridor scenario:
    (a) computed launch point, (b) delivery animation.}
  \label{fig:singlecluster_results}
\end{figure}
\subsection{Multiple Clusters – Multiple Corridors}
In this scenario, we deploy $N=39$ off‐route customers and use the elbow method with k-means++ to determine the optimal number of clusters, yielding $K=3$ (see Fig.~\ref{fig:elbow_method}a).  The resulting optimal launch points along the carrier path are
$
(500,0),\quad (0,2200),\quad (500,2000)$
for clusters~1, 2, and 3 respectively (Fig.~\ref{fig:pickup_points}b).  
Drone 1 serves the first cluster of 16 customers in four sorties, completing all deliveries in \SI{14200}{s}, while Drone 2 serves the second cluster of 12 customers in three sorties, finishing in \SI{16000}{s}, and Drone 3 handles the third cluster of 11 customers in three sorties, completing its deliveries in \SI{8000}{s}.  
\begin{figure}[h]
  \centering

  \begin{subfigure}[b]{0.42\textwidth}
    \includegraphics[width=\textwidth]{Results/elbow_method.png}
    \caption{Elbow method for \(k\) selection}
    \label{fig:elbow_method}
  \end{subfigure}
  \hfill
  % \begin{subfigure}[b]{0.42\textwidth}
  %   \includegraphics[width=\textwidth]{Results/cluster_pickup.png}
  %   \caption{Optimal pickup points for each cluster}
  %   \label{fig:pickup_points}
  % \end{subfigure}
\begin{subfigure}[b]{0.42\textwidth}
    \includegraphics[width=\textwidth]{Results/multi_cluster.png}
    \caption{Multi‐cluster, multi‐corridor snapshot}
    \label{fig:multicluster_animation}
  \end{subfigure}
  \vspace{1em}

 
  \begin{subfigure}[b]{0.42\textwidth}
    \includegraphics[width=\textwidth]{Results/flight gantt chart.png}
    \caption{Gantt chart of drone sorties}
    \label{fig:flight_gantt}
  \end{subfigure}
   \hfill
  \begin{subfigure}[b]{0.42\textwidth}
    \includegraphics[width=\textwidth]{Results/no_depot_cummalative.png}
    \caption{Cumulative customers served vs time taken (without depot stations}
    \label{fig:commulativ_customer in no depot stations}
  \end{subfigure}
  \caption{Summary of multi‐cluster, multi‐corridor results:
    (a) elbow method,(b) animation snapshot with pickup-point depiction, (c) sortie Gantt chart,(d) Commulative customers served w.r.t time taken (without depot stations).}
  \label{fig:multi_cluster_results}
\end{figure}
\subsection{Multi-Cluster, Multi-Corridor with Temporary Depot Stations}

In this scenario, we consider the same set of $N=39$ customer locations as before and apply k-means++ to partition them into three clusters.  For each cluster, we identify its optimal drone pickup point along the carrier’s route and install a temporary depot station at that position (Figure~\ref{fig:depot_position}).  These depots enable each drone to resupply payloads and recharge batteries between sorties, thereby reducing idle hover time and improving overall efficiency.

Figure~\ref{fig:depot_animation} shows a representative snapshot of the multi-cluster, multi-corridor delivery process with depot stations in place.  By comparing the Gantt charts in Figure~\ref{fig:depot_gantt}, we observe a  reduction in mission duration: the first drone now completes its assigned deliveries in approximately 6000 s, whereas the second and third drones each finish in roughly 12000 s—nearly a one-third-fold speedup relative to the no-depot case.  Finally, Figure~\ref{fig:customer_served} plots the cumulative number of customers served over time, highlighting the steeper service curves achieved when depot stations are used.
\begin{figure}[h]
    \centering
    % First row
    \begin{subfigure}[b]{0.42\linewidth}
        \centering
        \includegraphics[width=\linewidth]{Results/depot_position.png}
        \caption{Depot station locations}
        \label{fig:depot_position}
    \end{subfigure}
    \hfill
    \begin{subfigure}[b]{0.42\linewidth}
        \centering
        \includegraphics[width=\linewidth]{Results/depot_animation.png}
        \caption{Delivery snapshot with depots}
        \label{fig:depot_animation}
    \end{subfigure}

    \vspace{1em}

    % Second row
    \begin{subfigure}[b]{0.42\linewidth}
        \centering
        \includegraphics[width=\linewidth]{Results/depot_gantt_chart.png}
        \caption{Drone delivery Gantt chart}
        \label{fig:depot_gantt}
    \end{subfigure}
    \hfill
    \begin{subfigure}[b]{0.42\linewidth}
        \centering
        \includegraphics[width=\linewidth]{Results/customer served.png}
        \caption{Cumulative customers served vs time taken (with depot stations)}
        \label{fig:customer_served}
    \end{subfigure}

    \caption{Multi-cluster, multi-corridor results with temporary depot stations:
    (a) depot positions on the carrier route, (b) delivery snapshot,
    (c) per-drone delivery durations, (d) cumulative service curve.}
    \label{fig:all_depot_results}
\end{figure}

\section{Conclusion}\label{sec6}
We presented a corridor-style, cluster-based hybrid drone–carrier framework for last-mile delivery that constrains UAV paths to narrow, geofenced corridors, thereby reducing environmental disturbance and improving logistical efficiency. By confining drone trajectories to corridors rather than point-to-point flights, noise dispersion and ecological impacts are curtailed and airspace congestion is minimized. Customers are partitioned via $k$-means++, optimal pickup points are chosen along the carrier route, and intra-cluster tours are sequenced with a nearest-neighbor TSP heuristic followed by 2-OPT refinement, all while respecting battery endurance and payload capacity. We analyzed two operational cases: (i) drones return along the same corridor to rendezvous with the moving carrier after completing a sortie—hovering at the corridor mouth if necessary—and (ii) temporary depot stations are placed at the corridor mouth to provide recharging and package replenishment, eliminating drone hovering and unnecessary carrier returns.

Simulation results on urban road grids with depot stations show significant reductions in total drone flight distance and mission time compared with traditional point-to-point hybrid drone delivery, while maintaining battery and payload feasibility.

\subsection*{Author contributions}
F.Fatima contributed to the formulation, solution methodology, simulation results, and writing of the paper. PBS and DG provided the overall guidance in the formulation and solution methodology and the final write-up of the paper.
\subsection*{Funding}The authors did not receive support from any organization for the submitted work.
\section*{Declaration}
\subsection*{Ethics}Not applicable
\subsection*{Consent to participate}Not applicable
\subsection*{Consent to publish}Not applicable
\subsection*{Competing interests}The authors declare no competing interests.
\bibliography{sn-bibliography}% 
\end{document}

