Logistics has received considerable attention recently due to the rapid technological development of electronics and the Internet. Normally, clients expect items to be delivered at times that are convenient for their own schedules. Therefore, a multi-objective problem (MOP) model that simultaneously considers the depot desires and clients expectations can better elucidate the real logistics operations than a single objective model. This study proposes a MOP model based on VRP, in which two objective functions are run to minimize the total delivering path distance, while maximize client satisfaction by fulfilling time-window requirements. Moreover, this study proposes a hybrid algorithm based on GA incorporating some greedy algorithms to solve the developed MOP model with discrete variables. Besides, the response surface methodology (RSM) from design of experiments is adopted to help determine the crossover and mutation rates in GA. Finally, an actual military application is employed to confirm the practicality of the proposed MOP model and hybrid algorithm.