定向问题是路径优化问题中的一类,它意在有限的时间内从众多带收益客户中选择一组客户,规划车辆在这些客户间的服务线路来最大化地获取服务客户的收益,其本质是路径优化问题与背包问题的组合,该问题多用于服务环节耗时的应用,如旅行线路定制、无人机侦测线路优化、救援队搜救调度等。在现实问题中,客户的收益取决于多种因素,如服务的质量、收益的自然衰减以及动态变化等。基于这一观察,本文围绕收益随时间变化的假设,提出了定向问题的三种衍生问题,分别探讨了收益随服务时间变化时,如何选择客户、安排线路和分配服务时间;收益随服务时间和到达时间变化时,如何做以上三类决策;以及在服务时间不确定且收益随到达时间变化时,如何选择客户、安排线路。上述三个研究问题按照“先分析问题,再构造数学模型,最后设计和检验求解算法”的思路进行,研究方法综合使用精确算法、启发式算法以及它们的组合,根据问题性质和规模量身定制高效准确的求解算法,最后通过不同算法结果的比较来对求解方法进行评价。本文主要研究工作和结论归纳如下:（1）针对收益随服务时间变化的定向问题,提出一种禁忌搜索与精确算法混合的数学启发式算法。该算法将问题分解为路径优化子问题与服务时长分配子问题,二者进行迭代求解。路径优化子问题即为定向问题,使用禁忌搜索算法的框架来产生、改善线路;而对线路的评价由服务时间分配问题完成。针对一条已知线路,服务时间分配问题可建模为一个凸优化问题,通过KKT条件可推导出解析解,据此设计了一种多项式时间复杂度的精确求解算法。通过与已有多种精确算法比较,发现数学启发式算法能更加高效地找到最优或质量更好的解。（2）针对收益受到达时间与服务时间同时影响的团队定向问题,考虑收益与服务时间和到达时间之间的复杂非线性关系,建立了一个混合整数非线性规划模型,其中目标函数为非凹函数。针对该模型,提出了一种基于Benders分解的分支割平面法和两类缩小误差的有效不等式。此外,为扩大求解规模和提高计算速度,本文设计了一种使用迭代局部搜索和非梯度优化方法的混合元启发式算法,其中迭代局部搜索用来产生、改善线路,非梯度优化方法用来快速估算服务时间分配问题,完成对一条线路的评价。计算实验说明,基于Benders分解的分支割平面法显著优于求解器,有效割平面可以将误差缩小60%;相比于精确算法,混合元启发式算法能在10分钟内更找到最优或质量更好的解。（3）针对收益随到达时间影响的团队定向问题,考虑服务时间的不确定性,利用鲁棒优化思路进行建模,以帮助车辆能在特定不确定情况下肯定按时完成服务,并且取得最大收益,结合动态规划构造了一个混合整数线性规划模型。为求解该模型,设计了分支定价算法进行精确求解,其中根据客户非强制服务的特征,采用相应的分支策略,定价问题中采用带资源约束的部分最短路问题来进行加速。另外考虑大规模算例的求解,结合问题特征设计了禁忌搜索算法。实验结果表明,分支定价算法比其它精确算法更高效;禁忌搜索算法在求解质量上稍逊于BP算法,相差约为0.1%,但它在求解速度上的优势非常突出,所有算例均能在数秒内完成。另外,通过蒙特卡洛仿真产生大量不确定场景,实验结果显示由鲁棒模型所得线路更加可靠。主要创新点概括为以下三方面:首先,在求解收益随服务时间变化的定向问题上的算法创新。其次,提出了收益同时受服务时间和到达时间影响的团队定向问题,并分别设计了一种精确算法和一种启发式求解算法。最后,提出了在服务时间不确定环境下,收益随到达时间衰减的鲁棒团队定向问题,针对该问题采用鲁棒优化方法进行建模,并且设计了精确算法和启发式算法来求解。